Weighted odd-cycle transversals and fractional colorings of planar graphs

Abstract

We bound fractional chromatic numbers by establishing a connection with low-weight odd-cycle transversals. Let ℓ≥ 3 be an integer and let G be a graph of odd girth at least ℓ whose odd-cycle covering polyhedron is integral. For every nonnegative weight vector w=(w_v)_{v∈ V(G)}∈ ℝ_{≥ 0}^V(G), we obtain a set Z⊆ V(G) such that G−Z is bipartite and w(Z)≤mad(G)/2ℓw(V(G)). Here, w(S)=∑_{v∈ S}w_v for any S⊆ V(G), and mad(G) denotes the maximum average degree of G. Consequently, if mad(G)<2ℓ, then G has fractional chromatic number at most 4ℓ/(2ℓ−mad(G)). As applications, we prove that, for every positive integer k, every n-vertex planar graph of girth at least 2k+3 has fractional chromatic number at most (2k+1)/k(1−1/(kn+1)), establishing the girth version of Naserasr's fractional coloring conjecture with a strict inequality. For k=1, we furthermore prove that the upper bound 3n/(n+1) holds for every n-vertex triangle-free planar graph and this is attained for infinitely many values of n.

Total eight-colorings of maximal planar graphs of maximum degree six
Enqiang Zhu
arXiv27 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Fractional colorings of K_r-free graphs with local demands
Ewan Davies, Abhishek Dhawan, Abhishek Methuku +2
arXiv3 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Fractional DP-colorings of d-degenerate locally sparse graphs
Abhishek Dhawan, Huy Nguyen, Rohan A. Rathi
arXiv11 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Total dominating sets and four-colorings of planar triangulations
Hyemin Kwon, Boram Park, Yoshio Sano
arXiv1 Nov 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
Kengo Enami, Takahiro Matsushita
arXiv26 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{hu2026weighted,
  title = {{Weighted odd-cycle transversals and fractional colorings of planar graphs}},
  author = {Xiaolan Hu and Jiaao Li and Zhouningxin Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30719},
  eprint = {2610.30719},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30719},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Weighted odd-cycle transversals and fractional colorings of planar graphs
AU  - Xiaolan Hu
AU  - Jiaao Li
AU  - Zhouningxin Wang
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.30719
UR  - https://arxiv.org/abs/2610.30719
AB  - We bound fractional chromatic numbers by establishing a connection with low-weight odd-cycle transversals. Let ℓ≥ 3 be an integer and let G be a graph of odd girth at least ℓ whose odd-cycle covering polyhedron is integral. For every nonnegative weight vector w=(w_v)_v∈ V(G)∈ ℝ_≥ 0^V(G), we obtain a set Z⊆ V(G) such that G−Z is bipartite and w(Z)≤mad(G)/2ℓw(V(G)). Here, w(S)=∑_v∈ Sw_v for any S⊆ V(G), and mad(G) denotes the maximum average degree of G. Consequently, if mad(G)<2ℓ, then G has fractional chromatic number at most 4ℓ/(2ℓ−mad(G)). As applications, we prove that, for every positive integer k, every n-vertex planar graph of girth at least 2k+3 has fractional chromatic number at most (2k+1)/k(1−1/(kn+1)), establishing the girth version of Naserasr's fractional coloring conjecture with a strict inequality. For k=1, we furthermore prove that the upper bound 3n/(n+1) holds for every n-vertex triangle-free planar graph and this is attained for infinitely many values of n.
ER  -

Abstract

Related

Cite