Premium
Coloring rings
Author(s) -
Maffray Frédéric,
Penev Irena,
Vušković Kristina
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22635
Subject(s) - mathematics , combinatorics , conjecture , graph coloring , vertex (graph theory) , fractional coloring , complete coloring , discrete mathematics , brooks' theorem , chromatic scale , graph , class (philosophy) , 1 planar graph , chordal graph , graph power , line graph , computer science , artificial intelligence
A ring is a graph whose vertex set can be partitioned into k ≥ 4 nonempty sets, X 1 , … , X k , such that for all i ∈ { 1 , … , k } , the set X i can be ordered asX i = { u i 1 , … , u i | X i |}so that X i ⊆ N R [ u i ∣ X i ∣ ] ⊆ ⋯ ⊆ N R [ u i 1 ] = X i − 1 ∪ X i ∪ X i + 1 . A hyperhole is a ring R such that for all i ∈ { 1 , … , k } , X i is complete to X i − 1 ∪ X i + 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 et al [J. 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.