Colorings with neighborhood parity condition

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

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.

• Jezik: Angleški jezik
• Ključne besede: planar graphs, neighborhood, proper coloring, odd coloring
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2022
• Št. strani: Str. 385-391
• Številčenje: Vol. 321
• PID: 20.500.12556/RUL-144060
• UDK: 519.17
• ISSN pri članku: 0166-218X
• DOI: 10.1016/j.dam.2022.07.018
• COBISS.SI-ID: 139308803
• Datum objave v RUL: 30.01.2023

Gradivo je del revije

• Naslov: Discrete applied mathematics
• Skrajšan naslov: Discrete appl. math.
• Založnik: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: ravninski grafi, soseščina, dobro barvanje, liho barvanje

Projekti

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: P1-0383
• Naslov: Kompleksna omrežja

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: J1-3002
• Naslov: Prirejanja in barvanja povezav v kubičnih grafih