On Colorings of Squares of Outerplanar Graphs

2007/06/11 by Geir Agnarsson, Agnarsson, Geir, Magnús M. Halldórsson +2
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.0706.1526

24 pages, 17 figures

arxiv created 2007/06/11 · openalex publication_date 2007/06/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study vertex colorings of the square G² of an outerplanar graph G. We find the optimal bound of the inductiveness, chromatic number and the clique number of G² as a function of the maximum degree Δ of G for all Δ∈ \nats. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of G² when Δ≥ 7. In the case of chordal outerplanar graphs, we classify exactly which graphs have parameters exceeding the absolute minimum.

Related

• Injective chromatic number of outerplanar graphs
• Square Coloring of Planar Graphs with Maximum Degree at Most Five
• Further results on strong edge-colourings in outerplanar graphs
• Coloring squares of planar graphs with small maximum degree
• List total coloring of pseudo-outerplanar graphs