Acyclic Edge-Coloring of Planar Graphs
Data(s) |
2011
|
---|---|
Resumo |
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. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan Inform. Process. Lett., 108 (2008), pp. 412-417]. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/39203/1/ACYCLIC.pdf Basavaraju, Manu and Chandran, Sunil L and Cohen, Nathann and Havet, Frederic and Mueller, Tobias (2011) Acyclic Edge-Coloring of Planar Graphs. In: SIAM Journal on Discrete Mathematics, 25 (2). pp. 463-478. |
Publicador |
Society for Industrial and Applied Mathematics |
Relação |
http://epubs.siam.org/sidma/resource/1/sjdmec/v25/i2/p463_s1 http://eprints.iisc.ernet.in/39203/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |