Note on the hardness of rainbow connections for planar and line graphs (Q2350709)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6450191
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Note on the hardness of rainbow connections for planar and line graphs |
scientific article; zbMATH DE number 6450191 |
Statements
Note on the hardness of rainbow connections for planar and line graphs (English)
0 references
25 June 2015
0 references
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.
0 references
rainbow connection
0 references
rainbow vertex connection
0 references
NP-complete
0 references
planar graph
0 references
line graph
0 references
0.9326995
0 references
0.92863584
0 references
0.9285469
0 references
0.9248575
0 references
0.9219051
0 references
0.9068711
0 references
0 references
0.9055097
0 references
