Odd edge coloring of graphs

Authors

  • Borut Lužar Faculty of Information Studies, 8000 Novo mesto, Slovenia Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia
  • Mirko Petruševski Department of Mathematics and Informatics, Faculty of Mechanical Engineering - Skopje, Republic of Macedonia
  • Riste Škrekovski Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia Faculty of Information Studies, 8000 Novo mesto, Slovenia University of Primorska, FAMNIT, 6000 Koper, Slovenia

DOI:

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

Keywords:

Edge coloring, odd subgraph, edge decompositon.

Abstract

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.

Published

2014-12-28

Issue

Section

Articles