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

DOI10.1007/S40840-014-0077-XMaRDI QIDQ2350709zbMATH OpenOpenAlexFDO

Authors Xiaolong Huang, Yongtang Shi, Xueliang 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

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) Analysis of algorithms and problem complexity (68Q25)

Abstract: An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. It was proved that computing $rc(G)$ is an NP-Hard problem, as well as that even deciding whether a graph has $rc(G)=2$ is NP-Complete. It is known that deciding whether a given edge-colored graph is rainbow connected is NP-Complete. We will prove that it is still NP-Complete even when the edge-colored graph is a planar bipartite graph. We also give upper bounds of the rainbow connection number of outerplanar graphs with small diameters. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It is known that deciding whether a given vertex-colored graph is rainbow vertex-connected is NP-Complete. We will prove that it is still NP-Complete even when the vertex-colored graph is a line graph.

Review text

An edge-colored (vertex-colored, resp.) graph is rainbow connected (rainbow vertex-connected, resp.) if any two vertices are connected by a path whose edges (internal vertices, resp.) have distinct colors. Here, the colorings need not be proper. The first main theorem of this paper asserts that deciding whether a given edge-colored graph is rainbow connected is NP-complete in the class of planar, bipartite graphs. The second main result states that deciding whether a given vertex-colored graph is rainbow vertex-connected is NP-complete in the class of line graphs.

Recommendations

• Hardness results for total rainbow connection of graphs
• Rainbow connectivity: hardness and tractability
• Hardness result for the total rainbow \(k\)-connection of graphs
• Hardness and Algorithms for Rainbow Connectivity
• Further hardness results on the rainbow vertex-connection number of graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• The complexity of determining the rainbow vertex-connection of a graph

Cites work

• Graphs with rainbow connection number two
• Hardness and Algorithms for Rainbow Connectivity
• On minimally rainbow k-connected graphs
• On rainbow connection
• On the rainbow vertex-connection
• Rainbow connection in 3-connected graphs
• Rainbow connection in graphs
• Rainbow connection in graphs with minimum degree three
• Rainbow connection number and connected dominating sets
• Rainbow connection number and connectivity
• Rainbow connectivity: hardness and tractability
• The complexity of determining the rainbow vertex-connection of a graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited in

(24)

• Injective coloring of some graph operations
• More on the colorful monochromatic connectivity
• Proper connection number of graph products
• The \(k\)-proper index of graphs
• Rainbow connection numbers of Cayley digraphs on abelian groups
• On total rainbow \(k\)-connected graphs
• Complexity results for two kinds of colored disconnections of graphs
• Hardness results for three kinds of colored connections of graphs
• Total rainbow connection numbers of some special graphs
• Graphs with small total rainbow connection number
• On the complexity of \(k\)-rainbow cycle colouring problems
• The (k,)-rainbow index of random graphs
• Hardness results for total rainbow connection of graphs
• The complexity of determining the vertex-rainbow index of graphs
• Rainbow connections for outerplanar graphs with diameter 2 and 3
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Further hardness results on the rainbow vertex-connection number of graphs
• Hardness and algorithms for rainbow connection
• Algorithm on rainbow connection for maximal outerplanar graphs
• On various (strong) rainbow connection numbers of graphs
• Hardness and Algorithms for Rainbow Connectivity
• A survey on rainbow (vertex-)index of graphs
• The complexity of determining the rainbow vertex-connection of a graph
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs

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

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