Odd Colorings of Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915048250671104 |
|---|---|
| author | Cranston, Daniel W. |
| author_facet | Cranston, Daniel W. |
| contents | A proper coloring of a graph is called \emph{odd} if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. The smallest number of colors that admits an odd coloring of a graph $G$ is denoted $χ_o(G)$. This notion was introduced by Petruševski and Škrekovski, who proved that if $G$ is planar then $χ_o(G)\le 9$; they also conjectured that $χ_o(G)\le 5$. For a positive real number $α$, we consider the maximum value of $χ_o(G)$ over all graphs $G$ with maximum average degree less than $α$; we denote this value by $χ_o(\mathcal{G}_α)$. We note that $χ_o(\mathcal{G}_α)$ is undefined for all $α\ge 4$. In contrast, for each $α\in[0,4)$, we give a (nearly sharp) upper bound on $χ_o(\mathcal{G}_α)$. Finally, we prove $χ_o(\mathcal{G}_{20/7})= 5$ and $χ_o(\mathcal{G}_3)= 6$. Both of these results are sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_01455 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Odd Colorings of Sparse Graphs Cranston, Daniel W. Combinatorics 05C15 A proper coloring of a graph is called \emph{odd} if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. The smallest number of colors that admits an odd coloring of a graph $G$ is denoted $χ_o(G)$. This notion was introduced by Petruševski and Škrekovski, who proved that if $G$ is planar then $χ_o(G)\le 9$; they also conjectured that $χ_o(G)\le 5$. For a positive real number $α$, we consider the maximum value of $χ_o(G)$ over all graphs $G$ with maximum average degree less than $α$; we denote this value by $χ_o(\mathcal{G}_α)$. We note that $χ_o(\mathcal{G}_α)$ is undefined for all $α\ge 4$. In contrast, for each $α\in[0,4)$, we give a (nearly sharp) upper bound on $χ_o(\mathcal{G}_α)$. Finally, we prove $χ_o(\mathcal{G}_{20/7})= 5$ and $χ_o(\mathcal{G}_3)= 6$. Both of these results are sharp. |
| title | Odd Colorings of Sparse Graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2201.01455 |