Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.11555 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914718424236032 |
|---|---|
| author | Kitano, S. |
| author_facet | Kitano, S. |
| contents | An odd coloring of a graph $G$ is a proper vertex coloring $φ$ with the property that for each non-isolated vertex $v\in V(G)$, there exists a color $c$ such that the cardinality of $φ^{-1}(c)\cap N(v)$ is odd. The concept of odd colorings is introduced by Petruševski and Škrekovski. In this paper, we investigate upper bounds of the odd chromatic number of a graph in terms of its thickness and other graphical parameters. In particular, we show that a graph $G$ with the minimum degree at least $2θ(G)-1$ and girth at least $6$ is odd $6θ(G)$-colorable, where $θ(G)$ is the thickness of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11555 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper Bounds of the Odd Chromatic Number of a Graph in terms of its Thickness Kitano, S. Combinatorics An odd coloring of a graph $G$ is a proper vertex coloring $φ$ with the property that for each non-isolated vertex $v\in V(G)$, there exists a color $c$ such that the cardinality of $φ^{-1}(c)\cap N(v)$ is odd. The concept of odd colorings is introduced by Petruševski and Škrekovski. In this paper, we investigate upper bounds of the odd chromatic number of a graph in terms of its thickness and other graphical parameters. In particular, we show that a graph $G$ with the minimum degree at least $2θ(G)-1$ and girth at least $6$ is odd $6θ(G)$-colorable, where $θ(G)$ is the thickness of $G$. |
| title | Upper Bounds of the Odd Chromatic Number of a Graph in terms of its Thickness |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.11555 |