Colorings with neighborhood parity condition

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

Povzetek

V tem članku vpeljemo novo barvanje vozlišč, za katerega izhaja motivacija iz naše serije člankov o lihem barvanju povezav grafov. Pravilno barvanje vozlišč ▫$\varphi$▫ grafa ▫$G$▫ je liho, če za vsako neizolirano vozlišče ▫$x \in V(G)$▫ obstaja barva ▫$c$▫ za katero je množica ▫$\varphi^{-1}(c) \cap N(x)$▫ lihe velikosti. Dokažemo, da vsak enostaven ravninski graf dopušča liho 9-barvanje in domnevamo, da bo 5 barv vedno zadostovalo.

Ključne besede

ravninski grafi;soseščina;dobro barvanje;liho barvanje;planar graphs;neighborhood;proper coloring;odd coloring;

Podatki

Jezik:	Angleški jezik
Leto izida:	2022
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	139308803
ISSN:	0166-218X
Št. ogledov:	18
Št. prenosov:	8
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Barvanja s parnostnim pogojem v soseščini
Sekundarni povzetek:	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.
Sekundarne ključne besede:	ravninski grafi;soseščina;dobro barvanje;liho barvanje;
Vrsta dela (COBISS):	Članek v reviji
Strani:	str. 385-391
Zvezek:	ǂVol. ǂ321
Čas izdaje:	Nov. 2022
DOI:	10.1016/j.dam.2022.07.018
ID:	17881034