Idioma:

Acyclic edge-colouring of planar graphs

Basavaraju, Manu ; Chandran, L. Sunil ; Cohen, Nathann ; Havet, Frédéric ; Müller, Tobias

SIAM journal on discrete mathematics, 2011, Vol.25 (2), p.436-478 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Acyclic edge-colouring of planar graphs
Autor: Basavaraju, Manu ; Chandran, L. Sunil ; Cohen, Nathann ; Havet, Frédéric ; Müller, Tobias
Assuntos: Computer Science ; Discrete Mathematics
É parte de: SIAM journal on discrete mathematics, 2011, Vol.25 (2), p.436-478
Descrição: A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted χa′(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Δ(G) is large enough, then χa′(G) = Δ(G). We settle this conjecture for planar graphs with girth at least 5. We also show that χa′(G) ≤ Δ(G)+12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan [Inform. Process. Lett., 108 (2008), pp. 412-417].
Editor: Society for Industrial and Applied Mathematics
Idioma: Inglês

Links

Voltar para lista de resultados