Three-coloring and list three-coloring of graphs without induced paths on seven vertices (Q1786047)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Three-coloring and list three-coloring of graphs without induced paths on seven vertices |
scientific article |
Statements
Three-coloring and list three-coloring of graphs without induced paths on seven vertices (English)
0 references
24 September 2018
0 references
A graph \(G\) is \(H\)-free if \(G\) does not contain an induced subgraph isomorphic to \(H\). It is known that if \(H\) contains a cycle, then \(k\) -coloring is NP-complete for \(k\geq 3\) for the class of \(H\)-free graphs. In contrast, it is proved in this paper that one can decide whether a given \(P_{7}\)-free graph has a \(3\)-coloring and can find such a coloring, if any, in polynomial time.
0 references
coloring
0 references
list coloring
0 references
\(H\)-free graphs
0 references
complexity
0 references