On strong odd colorings of sparse graphs

Abstract

A strong odd coloring of a graph is a proper vertex coloring such that for every vertex v, each color appearing on the neighborhood of v appears an odd number of times. We investigate strong odd colorings of sparse graphs, where sparsity of a graph G is measured in terms of maximum average degree, denoted mad(G). We prove that the optimal threshold on the maximum average degree guaranteeing a strong odd c-coloring is 4−Θ(1/c) as c→∞. Moreover, for every c≥ 5, this threshold is strictly smaller than the threshold for odd c-coloring. We also determine the sharp threshold on the maximum average degree guaranteeing a strong odd $5$-coloring: every graph G with mad(G)<7/3 has a strong odd $5$-coloring, and this bound is sharp. In addition, we show that every graph G with mad(G)<11/5 and no induced $5$-cycle has a strong odd $4$-coloring. Note that the $5$-cycle has maximum average degree 2 and no strong odd $4$-coloring.

Fractional DP-colorings of d-degenerate locally sparse graphs
Abhishek Dhawan, Huy Nguyen, Rohan A. Rathi
arXiv11 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Thresholds and Fluctuations for Colorful Arithmetic Progressions in Sparse Random Colorings
Bhaswar B. Bhattacharya, Sanchayan Bhowal, Atmadeep Sengupta
arXiv28 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & 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
On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Optimal K_t-free list colorings and the Pollyanna property of graphs with no triangular wheel
Hongyang Wang, Rong Wu
arXiv26 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{choi2026strong,
  title = {{On strong odd colorings of sparse graphs}},
  author = {Ilkyoo Choi and Hojin Chu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34874},
  eprint = {2610.34874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34874},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On strong odd colorings of sparse graphs
AU  - Ilkyoo Choi
AU  - Hojin Chu
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.34874
UR  - https://arxiv.org/abs/2610.34874
AB  - A strong odd coloring of a graph is a proper vertex coloring such that for every vertex v, each color appearing on the neighborhood of v appears an odd number of times. We investigate strong odd colorings of sparse graphs, where sparsity of a graph G is measured in terms of maximum average degree, denoted mad(G). We prove that the optimal threshold on the maximum average degree guaranteeing a strong odd c-coloring is 4−Θ(1/c) as c→∞. Moreover, for every c≥ 5, this threshold is strictly smaller than the threshold for odd c-coloring. We also determine the sharp threshold on the maximum average degree guaranteeing a strong odd $5$-coloring: every graph G with mad(G)<7/3 has a strong odd $5$-coloring, and this bound is sharp. In addition, we show that every graph G with mad(G)<11/5 and no induced $5$-cycle has a strong odd $4$-coloring. Note that the $5$-cycle has maximum average degree 2 and no strong odd $4$-coloring.
ER  -

Abstract

Related

Cite