Strong odd coloring of sparse graphs

Mathematics > Combinatorics [Submitted on 22 Jan 2024 (v1), last revised 16 Jun 2026 (this version, v3)] Title:Strong odd coloring of sparse graphs View PDF HTML (experimental)Abstract:An odd coloring of a graph $G$ is a proper coloring of $G$ such that for every non-isolated vertex $v$, there is a color appearing an odd number of times in $N_G(v)$. Odd coloring of graphs was studied intensively in recent few years. In this paper, we introduce the notion of a strong odd coloring, as not only a strengthened version of odd coloring, but also a relaxation of square coloring. A strong odd coloring of a graph $G$ is a proper coloring of $G$ such that for every non-isolated vertex $v$, if a color appears in $N_G(v)$, then it appears an odd number of times in $N_G(v)$. We denote by $\chi_{so}(G)$ the smallest integer $k$ such that $G$ admits a strong odd coloring with $k$ colors. We prove that if $G$ is a graph with $mad(G)\le\frac{20}{7}$, then $\chi_{so}(G)\le \Delta(G)+4$, and the bound is tight. We also prove that if $G$ is a $C_4$-free graph with $mad(G)\le\frac{30}{11}$, then $\chi_{so}(G)\le \Delta(G)+3$. Submission history From: Hyemin Kwon [view email][v1] Mon, 22 Jan 2024 02:20:56 UTC (93 KB) [v2] Tue, 23 Jan 2024 04:16:36 UTC (93 KB) [v3] Tue, 16 Jun 2026 01:28:06 UTC (85 KB) References & Citations Loading... Bibliographic and Citation Tools Bibliographic Explorer (What is the Explorer?) Connected Papers (What is Connected Papers?) Litmaps (What is Litmaps?) scite Smart Citations (What are Smart Citations?) Code, Data and Media Associated with this Article alphaXiv (What is alphaXiv?) CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub (What is DagsHub?) Gotit.pub (What is GotitPub?) Hugging Face (What is Huggingface?) ScienceCast (What is ScienceCast?) Demos Recommenders and Search Tools Influence Flower (What are Influence Flowers?) CORE Recommender (What is CORE?) arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.