Hardness results for three kinds of colored connections of graphs

DOI10.1016/J.TCS.2020.06.030MaRDI QIDQ2202016zbMATH OpenOpenAlexFDO

Authors Zhong Huang, Xueliang Li

Publication date 17 September 2020

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

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

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)

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.

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
• Rainbow connectivity: hardness and tractability

Cites work

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

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)