Geodesic
Odd edge coloring of graphs
Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 267-277.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.576.895
Keywords: Edge coloring, odd subgraph, edge decompositon. 
@article{10_26493_1855_3974_576_895,
     author = {Borut Lu\v{z}ar and Mirko Petru\v{s}evski and Riste \v{S}krekovski},
     title = {Odd edge coloring of graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {267--277},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2015},
     doi = {10.26493/1855-3974.576.895},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.576.895/}
}
TY  - JOUR
AU  - Borut Lužar
AU  - Mirko Petruševski
AU  - Riste Škrekovski
TI  - Odd edge coloring of graphs
JO  - Ars Mathematica Contemporanea
PY  - 2015
SP  - 267
EP  - 277
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.576.895/
DO  - 10.26493/1855-3974.576.895
LA  - en
ID  - 10_26493_1855_3974_576_895
ER  - 
%0 Journal Article
%A Borut Lužar
%A Mirko Petruševski
%A Riste Škrekovski
%T Odd edge coloring of graphs
%J Ars Mathematica Contemporanea
%D 2015
%P 267-277
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.576.895/
%R 10.26493/1855-3974.576.895
%G en
%F 10_26493_1855_3974_576_895
Borut Lužar; Mirko Petruševski; Riste Škrekovski. Odd edge coloring of graphs. Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 267-277. doi : 10.26493/1855-3974.576.895. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.576.895/

Cité par Sources :