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 do periódico: Anais
- Conference titles: Encontro de Teoria da Computação - ETC
- Este periódico é de assinatura
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: bronze
-
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 maio 2024. -
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 2024 maio 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 2024 maio 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
- A practical minimal perfect hashing method
- Evolution of random subgraphs of the cube
- On Richardson's model on the hypercube
- The Turan theorem for random graphs
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Universality and tolerance
- Hereditary properties of triple systems
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