Premium
Circular coloring and fractional coloring in planar graphs
Author(s) -
Hu Xiaolan,
Li Jiaao
Publication year - 2022
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.22742
Subject(s) - mathematics , combinatorics , conjecture , homomorphism , planar graph , girth (graph theory) , counterexample , discrete mathematics , graph coloring , integer (computer science) , prime (order theory) , graph , computer science , programming language
Abstract We study the following Steinberg‐type problem on circular coloring: for an odd integer k ≥ 3 , what is the smallest number f ( k ) such that every planar graph of girth k without cycles of length from k + 1 to f ( k ) admits a homomorphism to the odd cycle C k (or equivalently, is circular ( k , k − 1 2 ) ‐colorable). Known results and counterexamples on Steinberg's Conjecture indicate that f ( 3 ) ∈ { 6 , 7 } . In this paper, we show that f ( k ) exists if and only if k is an odd prime. Moreover, we prove that for any prime p ≥ 5 , p 2 − 5 2 p + 3 2 ≤ f ( p ) ≤ 2 p 2 + 2 p − 5 . We conjecture that f ( p ) ≤ p 2 − 2 p , and observe that the truth of this conjecture implies Jaeger's conjecture that every planar graph of girth 2 p − 2 has a homomorphism to C p for any prime p ≥ 5 . Supporting this conjecture, we prove a related fractional coloring result that every planar graph of girth k without cycles of length from k + 1 to ⌊ 22 k 3 ⌋ is fractional ( k : k − 1 2 ) ‐colorable for any odd integer k ≥ 5 .