A Note on Odd Colorings of 1-Planar Graphs

DOI10.1016/J.DAM.2023.01.011MaRDI QIDQ6390229arXivFDO

Authors Daniel W. Cranston, Michael Lafferty, Z. X. Song

Publication date 5 February 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DAM.2023.01.011

Mathematics Subject Classification ID

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

arXiv classification

math.CO

Abstract: A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. This notion was recently introduced by Petruv{s}evski and v{S}krekovski, who proved that every planar graph admits an odd $9$-coloring; they also conjectured that every planar graph admits an odd $5$-coloring. Shortly after, this conjecture was confirmed for planar graphs of girth at least seven by Cranston; outerplanar graphs by Caro, Petruv{s}evski, and v{S}krekovski. Building on the work of Caro, Petruv{s}evski, and v{S}krekovski, Petr and Portier then further proved that every planar graph admits an odd $8$-coloring. In this note we prove that every 1-planar graph admits an odd $23$-coloring, where a graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge.

This page was built for publication: A Note on Odd Colorings of 1-Planar Graphs

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