Hardness results for three kinds of colored connections of graphs

DOI10.1016/J.TCS.2020.06.030zbMATH Open1455.68140arXiv2001.01948OpenAlexW3040599388MaRDI QIDQ2202016FDOQ2202016

Xueliang Li, Zhong Huang

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The concept of rainbow connection number of a graph was introduced by Chartrand et al. in 2008. Inspired by this concept, other concepts on colored version of connectivity in graphs were introduced, such as the monochromatic connection number by Caro and Yuster in 2011, the proper connection number by Borozan et al. in 2012, and the conflict-free connection number by Czap et al. in 2018, as well as some other variants of connection numbers later on. Chakraborty et al. proved that to compute the rainbow connection number of a graph is NP-hard. For a long time, it has been tried to fix the computational complexity for the monochromatic connection number, the proper connection number and the conflict-free connection number of a graph. However, it has not been solved yet. Only the complexity results for the strong version, i.e., the strong proper connection number and the strong conflict-free connection number, of these connection numbers were determined to be NP-hard. In this paper, we prove that to compute each of the monochromatic connection number, the proper connection number and the conflict free connection number for a graph is NP-hard. This solves a long standing problem in this field, asked in many talks of workshops and papers.

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

Recommendations

• Hardness and algorithms for rainbow connection
• Hardness and Algorithms for Rainbow Connectivity
• Note on the hardness of rainbow connections for planar and line graphs
• On the complexity of rainbow coloring problems
• Rainbow connectivity: hardness and tractability

zbMATH Keywords

complexityNP-hardnessmonochromatic connection numberproper connection numberconflict-free connection number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• Graph theory
• Rainbow connections of graphs: a survey
• Rainbow connection in graphs
• Hardness and algorithms for rainbow connection
• The complexity of satisfiability problems
• Characterizations of graphs having large proper connection numbers
• On proper-path colorings in graphs
• Proper connection of graphs
• Colorful monochromatic connectivity
• Monochromatic connecting colorings in strongly connected oriented graphs
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Properly Colored Connectivity of Graphs
• Proper connection number of random graphs
• More on the colorful monochromatic connectivity
• The (vertex-)monochromatic index of a graph
• Conflict-free connections of graphs
• Conflict-free connection numbers of line graphs
• On conflict-free connection of graphs
• (Strong) conflict-free connectivity: algorithm and complexity
• Minimum degree condition for proper connection number 2
• On the (di)graphs with (directed) proper connection number two
• On strong proper connection number of cubic graphs

Cited In (13)

• Constructive generation of very hard 3-colorability instances
• The proper 2-connection number and size of graphs
• Conflict-free connection number of graphs with four bridges
• The fine-grained complexity of approximately counting proper connected colorings (extended abstract)
• Constraining MC-numbers by the connectivity of complement graphs
• Monochromatic vertex-disconnection colorings of graphs
• Rainbow monochromatic \(k\)-edge-connection colorings of graphs
• The proper 2-connection number of several graph classes
• Conflict-free connection number and size of graphs
• (1, 2)-rainbow connection number at most 3 in connected dense graphs
• A survey on conflict-free connection coloring of graphs
• Hard-to-color graphs for connected sequential colorings
• Rainbow and monochromatic vertex-connection of random graphs

This page was built for publication: Hardness results for three kinds of colored connections of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2202016)