Abstract
Refining a bound by Lih, Wang and Zhu, we prove that if the square G2 of a K4-minor-free graph G with maximum degree Δ ≥ 6 does not contain a complete subgraph on ⌊ frac(3, 2) Δ ⌋ + 1 vertices, then G2 is ⌊ frac(3, 2) Δ ⌋-colorable.
Original language | English (US) |
---|---|
Pages (from-to) | 6572-6584 |
Number of pages | 13 |
Journal | Discrete Mathematics |
Volume | 309 |
Issue number | 23-24 |
DOIs | |
State | Published - Dec 6 2009 |
Keywords
- Brooks-type bound
- Chromatic number
- Series-parallel graph
- Square of a graph
- Vertex coloring
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics