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

Resumo

Uma coloração ímpar de um grafo G é uma atribuição de cores às arestas de G de modo que cada vértice é incidente a zero ou a um número ímpar de arestas de cada cor. O menor número de cores necessário em uma tal coloração é chamado de índice cromático ímpar de G e é denotado por χ_o'(G). Esse conceito foi definido por Pyber, que mostrou que χ_o'(G) ≤ 4 vale para todo grafo G. Nesse artigo, nós mostramos que quase todo grafo com número par (resp. ímpar) de vértices satisfaz χ_o'(G) = 2 (resp. χ_o'(G) = 3).

Palavras-chave: coloração de arestas, teoria dos grafos, grafos aleatórios

Referências

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