The odd chromatic index of almost all graphs - Botler, Fábio; Colucci, Lucas; Kohayakawa, Yoshiharu (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2020.11087, 2020)
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).