The odd chromatic index of almost all graphs

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
Publicado
30/06/2020
BOTLER, Fábio; COLUCCI, Lucas; KOHAYAKAWA, Yoshiharu. The odd chromatic index of almost all graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 49-52. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2020.11087.