Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-12T13:00:10.993Z Has data issue: false hasContentIssue false
  • English
  • Français

ACYCLIC COLOURINGS OF PLANAR GRAPHS WITH LARGE GIRTH

Published online by Cambridge University Press:  01 October 1999

O. V. BORODIN ,
A. V. KOSTOCHKA  and
D. R. WOODALL
O. V. BORODIN
Affiliation:
Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk 630090, Russia
A. V. KOSTOCHKA
Affiliation:
Novosibirsk State University, Novosibirsk 630090, Russia
D. R. WOODALL
Affiliation:
Department of Mathematics, University of Nottingham, Nottingham NG7 2RD
Get access

Abstract

A proper vertex-colouring of a graph is acyclic if there are no 2-coloured cycles. It is known that every planar graph is acyclically 5-colourable, and that there are planar graphs with acyclic chromatic number χa = 5 and girth g = 4. It is proved here that a planar graph satisfies χa [les ] 4 if g [ges ] 5 and χa [les ] 3 if g [ges ] 7.

Type
Notes and Papers
Information
Journal of the London Mathematical Society , Volume 60 , Issue 2 , October 1999 , pp. 344 - 352
Copyright
The London Mathematical Society 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)