The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- The proper conflict-free -coloring problem and the odd -coloring problem are NP-complete on bipartite graphsDiscrete Applied Mathematics, 2025
- Asymptotically Optimal Proper Conflict‐Free ColoringRandom Structures & Algorithms, 2025
- Proper conflict-free coloring of sparse graphsDiscrete Applied Mathematics, 2024
- Relaxation of Wegner’s planar graph conjecture for maximum degree 4Discrete Applied Mathematics, 2024
- On odd colorings of sparse graphsDiscrete Applied Mathematics, 2023
- The Odd Chromatic Number of a Planar Graph is at Most 8Graphs and Combinatorics, 2023
- A note on odd colorings of 1-planar graphsDiscrete Applied Mathematics, 2023
- Remarks on proper conflict-free colorings of graphsDiscrete Mathematics, 2022
- Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoodsDiscrete Applied Mathematics, 2022
- Colorings with neighborhood parity conditionDiscrete Applied Mathematics, 2022