Odd edge coloring of graphs

Borut Lužar, Mirko Petruševski, Riste Škrekovski


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 [5], 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 [3, 2]. 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.


Edge coloring, odd subgraph, edge decompositon.

Full Text:


DOI: https://doi.org/10.26493/1855-3974.576.895

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications