Odd colourings, conflict-free colourings and strong colouring numbers

MaRDI QIDQ6072045zbMATH OpenFDO

Authors Robert Hickingbotham

Publication date 29 November 2023

Full work available at URL https://arxiv.org/abs/2203.10402, http://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p160.pdf

zbMATH Keywords

conflict-free chromatic numberodd chromatic number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On odd colorings of sparse graphs
• The odd chromatic number of a planar graph is at most 8
• 1-planar graphs are odd 13-colorable
• An improvement of the bound on the odd chromatic number of 1-planar graphs
• Odd colorings of sparse graphs

Cites work

• Acyclic and oriented chromatic numbers of graphs
• Boxicity, poset dimension, and excluded minors
• Characterisations and examples of graph classes with bounded expansion
• Colorings with neighborhood parity condition
• Colouring graphs with bounded generalized colouring number
• Grad and classes with bounded expansion. I: Decompositions
• Graphs with linearly bounded Ramsey numbers
• Improper colourings inspired by Hadwiger's conjecture
• Odd coloring of sparse graphs and planar graphs
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Orderings on graphs and game coloring number
• Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Radius two trees specify χ‐bounded classes
• Remarks on odd colorings of graphs
• Remarks on proper conflict-free colorings of graphs
• Sparsity. Graphs, structures, and algorithms
• Strongly sublinear separators and polynomial expansion
• Sublinear separators in intersection graphs of convex shapes
• The odd chromatic number of a planar graph is at most 8

Cited in

(14)

• On odd colorings of sparse graphs
• Relaxation of Wegner's planar graph conjecture for maximum degree 4
• Brooks-type theorems for relaxations of square colorings
• Proper conflict-free coloring of graphs with large maximum degree
• New bounds for odd colourings of graphs
• On asymptotically tight bound for the conflict-free chromatic index of nearly regular graphs
• Cop-width, flip-width and strong colouring numbers
• Boundedness for proper conflict-free and odd colorings
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• Strong odd colorings in graph classes of bounded expansion
• The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
• Proper conflict-free 6-coloring of planar graphs without short cycles
• On strong odd colorings of graphs
• Asymptotically optimal proper conflict-free coloring

This page was built for publication: Odd colourings, conflict-free colourings and strong colouring numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072045)