zbMATH — the first resource for mathematics

Odd edge-colorability of subcubic graphs. (English) Zbl 1347.05057
Summary: An edge-coloring of a graph $$G$$ is said to be odd if for each vertex $$v$$ of $$G$$ and each color $$c$$, the vertex $$v$$ either uses the color $$c$$ an odd number of times or does not use it at all. The minimum number of colors needed for an odd edge-coloring of $$G$$ is the odd chromatic index $$\chi_o^{\prime}(G)$$. These notions were introduced by L. Pyber [in: Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company. 583–610 (1992; Zbl 0792.05110)], who showed that 4 colors suffice for an odd edge-coloring of any simple graph. In this paper, we consider loopless subcubic graphs, and give a complete characterization in terms of the value of their odd chromatic index.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: