Acyclic colourings of planar graphs with large girth

Authors
Borodin, OV Kostochka, AV Woodall, DR
Citation
Ov. Borodin et al., Acyclic colourings of planar graphs with large girth, J LOND MATH, 60, 1999, pp. 344-352
Citations number
10
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES
ISSN journal
00246107 → ACNP
Volume
60
Year of publication
1999
Part
2
Pages
344 - 352
Database
ISI
SICI code
0024-6107(199910)60:<344:ACOPGW>2.0.ZU;2-P
Abstract
A proper vertex-colouring of a graph is acidic if there are no 2-coloured c ycles. It is known that every planar graph is acyclically 5-colourable. and that there are planar graphs with acyclic chromatic number chi (a) = 5 and girth g = 4. It is proved here that a planar graph satisfies chi (a) less than or equal to 4 if g greater than or equal to 5 and chi less than or equ al to 3 if g greater than or equal to 7.