On strong odd colorings of 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_ | 1866914963480641536 |
|---|---|
| author | Caro, Yair Petruševski, Mirko Škrekovski, Riste Tuza, Zsolt |
| author_facet | Caro, Yair Petruševski, Mirko Škrekovski, Riste Tuza, Zsolt |
| contents | A strong odd coloring of a simple graph $G$ is a proper coloring of the vertices of $G$ such that for every vertex $v$ and every color $c$, either $c$ is used an odd number of times in the open neighborhood $N_G(v)$ or no neighbor of $v$ is colored by $c$. The smallest integer $k$ for which $G$ admits a strong odd coloring with $k$ colors is the strong odd chromatic number, $χ_{soc}(G)$. These coloring notion and graph parameter were recently defined in [H. Kwon and B. Park, Strong odd coloring of sparse graphs, ArXiv:2401.11653v2]. We answer a question raised by the originators concerning the existence of a constant bound for the strong odd chromatic number of all planar graphs. We also consider strong odd colorings of trees, unicyclic graphs and graph products. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On strong odd colorings of graphs Caro, Yair Petruševski, Mirko Škrekovski, Riste Tuza, Zsolt Combinatorics A strong odd coloring of a simple graph $G$ is a proper coloring of the vertices of $G$ such that for every vertex $v$ and every color $c$, either $c$ is used an odd number of times in the open neighborhood $N_G(v)$ or no neighbor of $v$ is colored by $c$. The smallest integer $k$ for which $G$ admits a strong odd coloring with $k$ colors is the strong odd chromatic number, $χ_{soc}(G)$. These coloring notion and graph parameter were recently defined in [H. Kwon and B. Park, Strong odd coloring of sparse graphs, ArXiv:2401.11653v2]. We answer a question raised by the originators concerning the existence of a constant bound for the strong odd chromatic number of all planar graphs. We also consider strong odd colorings of trees, unicyclic graphs and graph products. |
| title | On strong odd colorings of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.02336 |