Colorings with neighborhood parity condition

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2022
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	139308803
ISSN:	0166-218X
Views:	18
Downloads:	8
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Barvanja s parnostnim pogojem v soseščini
Secondary 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 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.
Secondary keywords:	ravninski grafi;soseščina;dobro barvanje;liho barvanje;
Type (COBISS):	Article
Pages:	str. 385-391
Issue:	ǂVol. ǂ321
Chronology:	Nov. 2022
DOI:	10.1016/j.dam.2022.07.018
ID:	17881034