z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here