Total colourings of planar graphs with large girth

被引：51
作者：
Borodin, OV
Kostochka, AV
Woodall, DR
机构：
[1] Novosibirsk State Univ, Novosibirsk 630090, Russia
[2] Russian Acad Sci, Inst Math, Novosibirsk 630090, Russia
[3] Univ Nottingham, Dept Math, Nottingham NG7 2RD, England
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 1998年 / 19卷 / 01期
基金：
英国工程与自然科学研究理事会;
关键词：
D O I：
10.1006/eujc.1997.0152
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It is proved that if G is a planar graph with total (vertex-edge) chromatic number X-n, maximum degree Delta and girth g, then X-n = Delta + 1 Delta greater than or equal to 5 and g greater than or equal to 5, or Delta greater than or equal to 4 and g greater than or equal to 6, or Delta greater than or equal to 3 and g greater than or equal to 10. These results hold also for graphs in the projective plane, torus and Klein bottle. (C) 1998 Academic Press Limited.
引用
收藏
页码：19 / 24
页数：6
相关论文
共 16 条
  • [1] [Anonymous], 1968, USPEKHIMAT NAUK
  • [2] Behzad M., 1965, THESIS MICHIGAN STAT
  • [3] Borodin OV, 1997, J GRAPH THEOR, V26, P53, DOI 10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.3.CO
  • [4] 2-8
  • [5] BORODIN OV, 1989, J REINE ANGEW MATH, V394, P180
  • [6] BORODIN OV, IN PRESS J COMB TH B
  • [7] Chen D. L., 1994, COMBINATORICS GRAPH, P17
  • [8] Chetwynd A.G., 1990, PITMAN RES NOTES MAT, V218, P65
  • [9] Erd o P., 1979, Congr. Numer., V26, P125
  • [10] JENSEN TR, 1995, GRAPH COLORING PROBL, P88
12