Note on the hardness of rainbow connections for planar and line graphs

DOI10.1007/s40840-014-0077-xzbMath1317.05058arXiv1110.3147OpenAlexW1974802388MaRDI QIDQ2350709

Yongtang Shi, Xiaolong Huang, Xue Liang Li

Publication date: 25 June 2015

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

line graphNP-completeplanar graphrainbow connectionrainbow vertex connection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Related Items (17)

Hardness results for total rainbow connection of graphs ⋮ Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ Injective coloring of some graph operations ⋮ Graphs with small total rainbow connection number ⋮ More on the colorful monochromatic connectivity ⋮ On the complexity of \(k\)-rainbow cycle colouring problems ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Proper connection number of graph products ⋮ The \(k\)-proper index of graphs ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ Rainbow connection numbers of Cayley digraphs on abelian groups ⋮ On total rainbow \(k\)-connected graphs ⋮ Algorithm on rainbow connection for maximal outerplanar graphs ⋮ The complexity of determining the vertex-rainbow index of graphs ⋮ On various (strong) rainbow connection numbers of graphs ⋮ Total rainbow connection numbers of some special graphs ⋮ The \((k,\ell)\)-rainbow index of random graphs

Cites Work

• Rainbow connection in 3-connected graphs
• Rainbow connection number and connectivity
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• Rainbow connections of graphs: a survey
• On minimally rainbow \(k\)-connected graphs
• On the rainbow vertex-connection
• Rainbow connection number and connected dominating sets
• New Hardness Results in Rainbow Connectivity
• Graphs with rainbow connection number two
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Hardness and Algorithms for Rainbow Connectivity

This page was built for publication: Note on the hardness of rainbow connections for planar and line graphs