A Brooks-type bound for squares of K4-minor-free graphs

Alexandr V. Kostochka, Lale Özkahya, Douglas R. Woodall

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)6572-6584
Number of pages13
JournalDiscrete Mathematics
Volume309
Issue number23-24
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'A Brooks-type bound for squares of K<sub>4</sub>-minor-free graphs'. Together they form a unique fingerprint.

Cite this