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.

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