Note on the hardness of rainbow connections for planar and line graphs (Q2350709): Difference between revisions

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.