The odd chromatic index of almost all graphs (2020)
- Authors:
- USP affiliated authors: KOHAYAKAWA, YOSHIHARU - IME ; SOUZA, LUCAS COLUCCI CAVALCANTE DE - IME
- Unidade: IME
- DOI: 10.5753/etc.2020.11087
- Subjects: TEORIA DOS GRAFOS; GRAFOS ALEATÓRIOS
- Keywords: coloração de arestas
- Agências de fomento:
- Language: Inglês
- Abstract: 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).
- Imprenta:
- Publisher: SBC
- Publisher place: Porto Alegre
- Date published: 2020
- Source:
- Título: Anais
- Conference titles: Encontro de Teoria da Computação - ETC
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
BOTLER, Fábio Happ e COLUCCI, Lucas e KOHAYAKAWA, Yoshiharu. The odd chromatic index of almost all graphs. 2020, Anais.. Porto Alegre: SBC, 2020. Disponível em: https://doi.org/10.5753/etc.2020.11087. Acesso em: 13 fev. 2026. -
APA
Botler, F. H., Colucci, L., & Kohayakawa, Y. (2020). The odd chromatic index of almost all graphs. In Anais. Porto Alegre: SBC. doi:10.5753/etc.2020.11087 -
NLM
Botler FH, Colucci L, Kohayakawa Y. The odd chromatic index of almost all graphs [Internet]. Anais. 2020 ;[citado 2026 fev. 13 ] Available from: https://doi.org/10.5753/etc.2020.11087 -
Vancouver
Botler FH, Colucci L, Kohayakawa Y. The odd chromatic index of almost all graphs [Internet]. Anais. 2020 ;[citado 2026 fev. 13 ] Available from: https://doi.org/10.5753/etc.2020.11087 - The mod k chromatic index of random graphs
- The mod k chromatic index of graphs is O(k)
- The mod k chromatic index of random graphs
- On the zero-sum Ramsey problem over 'Z POT. d IND. 2'
- Weak hypergraph regularity and linear hypergraphs
- Property testing and parameter testing for permutations
- The induced size-Ramsey number of cycles
- An extension of the blow-up lemma to arrangeable graphs
- The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
- Regular pairs in sparse random graphs I
Informações sobre o DOI: 10.5753/etc.2020.11087 (Fonte: oaDOI API)
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3009839.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
