More on the rainbow disconnection in graphs

DOI10.7151/dmgt.2333zbMath1493.05092arXiv1810.09736OpenAlexW3033339074MaRDI QIDQ2158198

Zhong Huang, Renying Chang, Xue Liang Li, Xu Qing Bai

Publication date: 26 July 2022

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.09736

zbMATH Keywords

complexityedge-coloringNP-hardnessedge-connectivityErdős-Gallai type problemNordhaus-Gaddum type boundsrainbow disconnection coloring number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (3)

Monochromatic vertex-disconnection colorings of graphs ⋮ The proper vertex-disconnection of graphs ⋮ Complexity results for two kinds of colored disconnections of graphs

Cites Work

• Unnamed Item
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• Some criteria for a graph to be class 1
• Hardness and algorithms for rainbow connection
• The connectivity of a graph and its complement
• Rainbow disconnection in graphs
• Nordhaus-Gaddum inequalities for domination in graphs
• Rainbow connections of graphs: a survey
• A survey of Nordhaus-Gaddum type relations
• Ein Extremalproblem des Zusammenhangs von Graphen
• Circuits in critical graphs
• On Complementary Graphs
• Maximal Flow Through a Network
• Rainbow connection in graphs
• The NP-Completeness of Edge-Coloring
• Regular Graphs of High Degree are 1-Factorizable
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: More on the rainbow disconnection in graphs