Vertex coloring the square of outerplanar graphs of low degree

Geir Agnarsson*, Magńus M. Halld́orsson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ≠= 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

Original languageEnglish
Pages (from-to)619-636
Number of pages18
JournalDiscussiones Mathematicae - Graph Theory
Volume30
Issue number4
DOIs
Publication statusPublished - 2010

Other keywords

  • Chromatic number
  • Outerplanar
  • Power of a graph
  • Weak dual

Fingerprint

Dive into the research topics of 'Vertex coloring the square of outerplanar graphs of low degree'. Together they form a unique fingerprint.

Cite this