Edge colourings of embedded graphs without 4-cycles or chordal-4-cycles

Abstract

Let G be a simple graph embedded in a surface Σ of Euler characteristic χ(Σ)≥0, and let χ′(G) and Δ denote the chromatic index and the maximum degree of G, respectively. The paper shows that χ′(G)=Δ if Δ≥6 and G does not contain chordal-4-cycles or Δ≥5 and G does not contain 4-cycles.

Keywords:

• edge colouring
• chromatic index
• Euler characteristic
• cycle
• chord

2000 AMS Subject Classifications:

• 05C15
• 05C85

Acknowledgements

We would like to thank the referees for providing some very helpful suggestions for revising this paper. This work is supported by research grants NSFC(10871119), RFDP(200804220001) and NSFSP(Y2008A20) of China.

Additional information

Notes on contributors

Jianfeng Hou

Current address: Center for Discrete Mathematics, Fuzhou University, Fuzhou 350002, China