Strong odd coloring of sparse graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914648923570176 |
|---|---|
| author | Kwon, Hyemin Park, Boram |
| author_facet | Kwon, Hyemin Park, Boram |
| contents | 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 $χ_{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 $χ_{so}(G)\le Δ(G)+4$, and the bound is tight. We also prove that if $G$ is a graph with $mad(G)\le\frac{30}{11}$ and $Δ(G)\ge 4$, then $χ_{so}(G)\le Δ(G)+3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11653 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strong odd coloring of sparse graphs Kwon, Hyemin Park, Boram Combinatorics 05C15 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 $χ_{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 $χ_{so}(G)\le Δ(G)+4$, and the bound is tight. We also prove that if $G$ is a graph with $mad(G)\le\frac{30}{11}$ and $Δ(G)\ge 4$, then $χ_{so}(G)\le Δ(G)+3$. |
| title | Strong odd coloring of sparse graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2401.11653 |