The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916105780461568 |
|---|---|
| author | Anderson, James Chau, Herman Cho, Eun-Kyung Crawford, Nicholas Hartke, Stephen G. Heath, Emily Henderschedt, Owen Kwon, Hyemin Zhang, Zhiyuan |
| author_facet | Anderson, James Chau, Herman Cho, Eun-Kyung Crawford, Nicholas Hartke, Stephen G. Heath, Emily Henderschedt, Owen Kwon, Hyemin Zhang, Zhiyuan |
| contents | We introduce a new tool useful for greedy coloring, which we call the forb-flex method, and apply it to odd coloring and proper conflict-free coloring of planar graphs. The odd chromatic number, denoted $χ_{\mathsf{o}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing an odd number of times in its neighborhood. The proper conflict-free chromatic number, denoted $χ_{\mathsf{PCF}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing uniquely in its neighborhood. Our new tool works by carefully counting the structures in the neighborhood of a vertex and determining if a neighbor of a vertex can be recolored at the end of a greedy coloring process to avoid conflicts. Combining this with the discharging method allows us to prove $χ_{\mathsf{PCF}}(G) \leq 4$ for planar graphs of girth at least 11, and $χ_{\mathsf{o}}(G) \leq 4$ for planar graphs of girth at least 10. These results improve upon the recent works of Cho, Choi, Kwon, and Park. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14590 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs Anderson, James Chau, Herman Cho, Eun-Kyung Crawford, Nicholas Hartke, Stephen G. Heath, Emily Henderschedt, Owen Kwon, Hyemin Zhang, Zhiyuan Combinatorics We introduce a new tool useful for greedy coloring, which we call the forb-flex method, and apply it to odd coloring and proper conflict-free coloring of planar graphs. The odd chromatic number, denoted $χ_{\mathsf{o}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing an odd number of times in its neighborhood. The proper conflict-free chromatic number, denoted $χ_{\mathsf{PCF}}(G)$, is the smallest number of colors needed to properly color $G$ such that every non-isolated vertex of $G$ has a color appearing uniquely in its neighborhood. Our new tool works by carefully counting the structures in the neighborhood of a vertex and determining if a neighbor of a vertex can be recolored at the end of a greedy coloring process to avoid conflicts. Combining this with the discharging method allows us to prove $χ_{\mathsf{PCF}}(G) \leq 4$ for planar graphs of girth at least 11, and $χ_{\mathsf{o}}(G) \leq 4$ for planar graphs of girth at least 10. These results improve upon the recent works of Cho, Choi, Kwon, and Park. |
| title | The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.14590 |