2019/07/27 by Frédéric Maffray, Irena Penev, Maffray, Frédéric +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.11905
openalex publication_date 2019/07/27 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
A ring is a graph R whose vertex set can be partitioned into k ≥ 4 nonempty sets, X1, …, Xk, such that for all i ∈ \1,…,k\, the set Xi can be ordered as Xi = \ui1, …, ui|Xi|\ so that Xi ⊆ NR[ui|Xi|] ⊆ … ⊆ NR[ui1] = Xi-1 ∪ Xi ∪ Xi+1. A hyperhole is a ring R such that for all i ∈ \1,…,k\, Xi is complete to Xi-1∪ Xi+1. In this paper, we prove that the chromatic number of a ring R is equal to the maximum chromatic number of a hyperhole in R. Using this result, we give a polynomial-time coloring algorithm for rings. Rings formed one of the basic classes in a decomposition theorem for a class of graphs studied by Boncompagni, Penev, and Vušković in [Journal of Graph Theory 91 (2019), 192--246]. Using our coloring algorithm for rings, we show that graphs in this larger class can also be colored in polynomial time. Furthermore, we find the optimal χ-bounding function for this larger class of graphs, and we also verify Hadwiger's conjecture for it.