Odd edge coloring of graphs

english

2015

volume 9, issue 2

edge coloring   edge decompositon   odd subgraph

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

An edge coloring of a graph ?$G$? is said to be an odd edge coloring if for each vertex ?$v$? of ?$G$? and each color ?$c$?, the vertex ?$v$? uses the color ?$c$? an odd number of times or does not use it at all. In L. Pyber, Covering the edges of a graph by..., Graphs and Numbers, Colloq. Math. Soc. János Bolyai 60 (1991), 583-610., Pyber proved that 4 colors suffice for an odd edge coloring of any simple graph. Recently, some results on this type of colorings of (multi)graphs were successfully applied in solving a problem of facial parity edge coloring B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218-2222 and J. Czap, S. Jendrol', F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Disc. Math. 312 (2012), 2735-2740. In this paper we present additional results, namely we prove that 6 colors suffice for an odd edge coloring of any loopless connected (multi)graph, provide examples showing that this upper bound is sharp and characterize the family of loopless connected (multi)graphs for which the bound 6 is achieved. We also pose several open problems.

29.05.2020