Colorings with neighborhood parity condition

DOI10.1016/J.DAM.2022.07.018MaRDI QIDQ2172422zbMATH OpenOpenAlexFDO

Authors Mirko Petruševski, Riste Škrekovski

Publication date 15 September 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2112.13710

zbMATH Keywords

neighborhoododd coloringplanar graphproper coloring

Mathematics Subject Classification ID

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

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 $varphi$ of graph $G$ is said to be odd if for each non-isolated vertex $xinV(G)$ there exists a color $c$ such that $varph{i}^{-1}(c)capN(x)$ is odd-sized. We prove that every simple planar graph admits an odd $9$-coloring, and conjecture that $5$ colors always suffice.

Recommendations

• The odd chromatic number of a planar graph is at most 8
• Remarks on odd colorings of graphs
• Odd edge coloring of graphs
• scientific article; zbMATH DE number 7666240
• Odd coloring of sparse graphs and planar graphs

Cites work

• A note on weak odd edge-colorings of graphs
• Conflict-free coloring and its applications
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colouring of graphs
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free colourings of uniform hypergraphs with few edges
• Decomposition of a graph into two disjoint odd subgraphs
• Graph theory
• Graph unique-maximum and conflict-free colorings
• scientific article; zbMATH DE number 1021588 (Why is no real title available?)
• scientific article; zbMATH DE number 5237271 (Why is no real title available?)
• Odd 4-edge-colorability of graphs
• Odd decompositions and coverings of graphs
• Odd edge coloring of graphs
• Odd edge-colorability of subcubic graphs
• On vertex-parity edge-colorings
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Unique-maximum coloring of plane graphs

Cited in

(46)

• Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
• Remarks on proper conflict-free colorings of graphs
• Remarks on odd colorings of graphs
• A note on weak odd edge-colorings of graphs
• The odd chromatic number of a planar graph is at most 8
• Odd coloring of sparse graphs and planar graphs
• A note on odd colorings of 1-planar graphs
• Vertex colorings of graphs without short odd cycles
• Odd edge coloring of graphs
• Some new characterizations of graph colorability and of blocking sets of projective spaces
• Odd 4-edge-colorability of graphs
• scientific article; zbMATH DE number 915267 (Why is no real title available?)
• scientific article; zbMATH DE number 7666240 (Why is no real title available?)
• 1-planar graphs are odd 13-colorable
• On conflict-free proper colourings of graphs without small degree vertices
• Odd colourings, conflict-free colourings and strong colouring numbers
• On odd colorings of planar graphs
• An improvement of the bound on the odd chromatic number of 1-planar graphs
• On odd colorings of sparse graphs
• IC-planar graphs are odd-10-colorable
• Improper odd coloring of IC-planar graphs
• Odd 4-coloring of outerplanar graphs
• Brooks-type theorems for relaxations of square colorings
• Proper conflict-free coloring of sparse graphs
• New bounds for odd colourings of graphs
• A remark on a result on odd colorings of planar graphs
• New bounds for proper h-conflict-free colorings
• Odd coloring of 2-boundary planar graphs and beyond
• Boundedness for proper conflict-free and odd colorings
• The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
• On odd and strong odd colorings of graphs
• An improvement of the bound on the improper odd chromatic number of IC-planar graphs
• The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs
• Closed neighborhood balanced coloring of graphs
• On the parameterized complexity of odd coloring
• On strong odd colorings of graphs
• An odd 4-coloring of a maximal outerplanar graph
• Tight bounds on odd chromatic number of some standard graph products
• Odd chromatic number of graph classes
• Odd coloring of k-trees
• On odd coloring of graphs
• Strong odd coloring of sparse graphs
• On the parameterized complexity of odd coloring
• On a conjecture about the strong odd chromatic number of planar graphs
• Results on proper conflict-free list coloring of graphs
• 2-odd coloring of graphs with small maximum average degree

This page was built for publication: Colorings with neighborhood parity condition

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