Colorings with neighborhood parity condition

Petruševski, Mirko (author), Škrekovski, Riste (author)

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

• Language: English
• Keywords: planar graphs, neighborhood, proper coloring, odd coloring
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2022
• Number of pages: Str. 385-391
• Numbering: Vol. 321
• PID: 20.500.12556/RUL-144060
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2022.07.018
• COBISS.SI-ID: 139308803
• Publication date in RUL: 30.01.2023

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: ravninski grafi, soseščina, dobro barvanje, liho barvanje

Projects

• Funder: ARRS - Slovenian Research Agency
• Project number: P1-0383
• Name: Kompleksna omrežja

• Funder: ARRS - Slovenian Research Agency
• Project number: J1-3002
• Name: Prirejanja in barvanja povezav v kubičnih grafih