Coloring the square of a \(K_{4}\)-minor free graph (Q1402088)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Coloring the square of a \(K_{4}\)-minor free graph |
scientific article |
Statements
Coloring the square of a \(K_{4}\)-minor free graph (English)
0 references
19 August 2003
0 references
Let \(G\) be a \(K_4\)-minor free graph with maximum vertex degree \(\Delta\). The authors show that the chromatic number of the square of \(G\) is at most \(\Delta+ 3\) if \(2\leq\Delta\leq 3\), and \(\lfloor 3\Delta/2\rceil+ 1\) if \(\Delta\geq 4\). The result is best possible.
0 references
series-parallel graph
0 references
\(K_4\)-minor free graph
0 references
square
0 references
chromatic number
0 references
