Hardness results for three kinds of colored connections of graphs

DOI10.1016/j.tcs.2020.06.030zbMath1455.68140arXiv2001.01948OpenAlexW3040599388MaRDI QIDQ2202016

Zhong Huang, Xue Liang 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-hardnessproper connection numbermonochromatic connection numberconflict-free connection number

Mathematics Subject Classification ID

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

Related Items (8)

Monochromatic vertex-disconnection colorings of graphs ⋮ The proper 2-connection number and size of graphs ⋮ Conflict-free connection number of graphs with four bridges ⋮ (1, 2)-rainbow connection number at most 3 in connected dense graphs ⋮ Constraining MC-numbers by the connectivity of complement graphs ⋮ Rainbow monochromatic \(k\)-edge-connection colorings of graphs ⋮ Conflict-free connection number and size of graphs ⋮ Rainbow and monochromatic vertex-connection of random graphs

Cites Work

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

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