Odd coloring graphs with linear neighborhood complexity

2025/06/10 by James Davies, Davies, James, Meike Hatzel +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2506.08926

openalex publication_date 2025/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if G is the class of all circle graphs, or if G is any class with bounded twin-width, bounded merge-width, or a forbidden vertex-minor, then G is χ_o-bounded.

Citations

• Strong odd colorings in graph classes of bounded expansion
• Strong odd coloring in minor-closed classes
• Girth in GF(q)-representable matroids
• χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
• Merge-width and First-Order Model Checking
• Upper Bounds of the Odd Chromatic Number of a Graph in terms of its Thickness
• Strong odd coloring of sparse graphs
• Boundedness for proper conflict-free and odd colorings
• On the density of matroids omitting a complete-graphic minor
• New bounds for odd colourings of graphs
• Odd Chromatic Number of Graph Classes
• Odd chromatic number of graph classes
• Flipper games for monadically stable graph classes
• 1-planar graphs are odd 13-colorable
• The odd chromatic number of a toroidal graph is at most 9
• Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs
• Odd colourings, conflict-free colourings and strong colouring numbers
• Odd coloring of sparse graphs and planar graphs
• Graphs of bounded twin-width are quasi-polynomially χ-bounded
• Remarks on odd colorings of graphs
• Colorings with neighborhood parity condition
• Improved bounds for colouring circle graphs
• Vertex-minor-closed classes are χ-bounded
• Twin-width I: tractable FO model checking
• Erdos-Hajnal conjecture for graphs with bounded VC-dimension
• Characterising Bounded Expansion by Neighbourhood Complexity
• Unique-maximum and conflict-free colorings for hypergraphs and tree\n graphs

Related

• Boundedness for proper conflict-free and odd colorings
• Remarks on odd colorings of graphs
• Colorings with neighborhood parity condition
• Strong odd colorings in graph classes of bounded expansion
• Odd Chromatic Number of Graph Classes