Hardness results for three kinds of colored connections of graphs
DOI10.1016/j.tcs.2020.06.030zbMath1455.68140arXiv2001.01948OpenAlexW3040599388MaRDI QIDQ2202016
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
complexityNP-hardnessproper connection numbermonochromatic connection numberconflict-free connection number
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)
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