Acyclic edge-colouring of graphs (2025)
- Authors:
- Autor USP: PORRAS, ARIANA MAITE QUISPE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2025.tde-12012026-185219
- Subjects: ALGORITMOS GRÁFICOS; TEORIA DOS GRAFOS
- Keywords: Acyclic chromatic index; Acyclic edge colouring; Coloração acíclica de arestas; Índice cromático acíclico; Arestas (teoria dos grafos)
- Agências de fomento:
- Language: Inglês
- Abstract: Uma aresta-coloração própria de um grafo G é chamada acíclica se não existem ciclos bicromáticos em G. O índice cromático acíclico de um grafo simples G, denotado por a'(G), é o menor número k tal que G admite uma aresta-coloração acíclica usando k cores. Fiamik (1978) e Alon, Sudakov e Zaks (2001) conjeturaram independentemente que a'(G) (G) + 2 para qualquer grafo simples G. Esta conjectura é bem conhecida como a Conjectura da Coloração Acíclica de Arestas (AECC, sigla em inglês). Atualmente, o melhor limite superior para um grafo arbitrário é 3.569((G) - 1), obtido por Fialho, de Lima e Procacci (2020). Este resultado foi provado usando uma modificação do algoritmo de coloração de arestas apresentado por Giotis, Kirousis, Psaromiligkos e Thilikos (2017). Além disso, a AECC foi provada para grafos com {3,4}, grafos 2-degenerados, grafos 3-esparsos, para alguns casos de grafos completos e para alguns casos de grafos planares. O principal objetivo deste trabalho é estudar a AECC para os grafos com {3,4} e para grafos completos bipartidos K_{p,p} quando p é primo. Em particular, para o caso = 3, temos uma demonstração original e possivelmente mais legível do que as demonstrações nos artigos publicados. Infelizmente, no caso = 4, conseguimos limpar apenas alguns dos casos, uma vez que, novamente, a literatura sobre o caso é de leitura muito difícil
- Imprenta:
- Data da defesa: 13.11.2025
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
QUISPE PORRAS, Ariana Maite. Acyclic edge-colouring of graphs. 2025. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2025. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-12012026-185219/. Acesso em: 25 jan. 2026. -
APA
Quispe Porras, A. M. (2025). Acyclic edge-colouring of graphs (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-12012026-185219/ -
NLM
Quispe Porras AM. Acyclic edge-colouring of graphs [Internet]. 2025 ;[citado 2026 jan. 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-12012026-185219/ -
Vancouver
Quispe Porras AM. Acyclic edge-colouring of graphs [Internet]. 2025 ;[citado 2026 jan. 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-12012026-185219/
Informações sobre o DOI: 10.11606/D.45.2025.tde-12012026-185219 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
