The odd chromatic index of almost all graphs

• Fábio Botler UFRJ http://orcid.org/0000-0003-2028-199X
• Lucas Colucci
• Yoshiharu Kohayakawa IME-USP http://orcid.org/0000-0001-7841-157X

DOI: https://doi.org/10.5753/etc.2020.11087

Abstract

An odd coloring of a graph G is an assignment of colors to the edges of G in a way that each vertex is incident to either zero or an odd number of edges of each color. The minimum number of colors needed in such a coloring is called the odd chromatic index of G, and it is denoted by χ_o'(G). This notion was introduced by Pyber, who showed that χ_o'(G) ≤ 4 holds for every graph G. In this paper, we show that almost every graph on an even (resp. odd) number of vertices satisfies χ_o'(G) = 2 (resp. χ_o'(G) = 3).

Keywords: edge-colorings, graph theory, random graphs

References

Alon, N. and Spencer, J. H. (2004). The probabilistic method. John Wiley & Sons.

Kano, M., Katona, G. Y., and Varga, K. (2018). Decomposition of a graph into two

disjoint odd subgraphs. Graphs and Combinatorics, 34(6):1581–1588.

Korándi, D., Krivelevich, M., and Sudakov, B. (2015). Decomposing random graphs into few cycles and edges. Combinatorics, Probability and Computing, 24(6):857–872.

Lužar, B., Petruševski, M., and Škrekovski, R. (2014). Odd edge coloring of graphs. Ars Mathematica Contemporanea, 9(2):267–277.

Mátrai, T. (2006). Covering the edges of a graph by three odd subgraphs. Journal of Graph Theory, 53(1):77–82.

Petruševski, M. (2018). Odd 4-edge-colorability of graphs. Journal of Graph Theory, 87(4):460–474.

Pyber, L. (1991). Covering the edges of a graph by . . . . In Sets, Graphs and Numbers, Colloquia Mathematica Societatis János Bolyai, volume 60, pages 583–610.

Scott, A. D. (1997). On graph decompositions modulo k. Discrete Mathematics, 175(1-3):289–291