Colorings with neighborhood parity condition

2021/12/27 by Petruševski, Mirko, Škrekovski, Riste · 4 citations
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2112.13710

Abstract

In this short paper, we introduce a new vertex coloring whose motivation comes from our series on odd edge-colorings of graphs. A proper vertex coloring φ of graph G is said to be odd if for each non-isolated vertex x∈ V(G) there exists a color c such that φ^-1(c)∩ N(x) is odd-sized. We prove that every simple planar graph admits an odd 9-coloring, and conjecture that 5 colors always suffice.

Cited by

• Chromatic numbers with open and nonzero local modular constraints
• Results on proper conflict-free list coloring of graphs
• Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
• Odd coloring graphs with linear neighborhood complexity

Related

• Remarks on odd colorings of graphs
• Odd coloring of sparse graphs and planar graphs
• On strong odd colorings of graphs
• 1-planar graphs are odd 13-colorable
• Odd coloring graphs with linear neighborhood complexity