A bound on the total chromatic number

被引：67
|
作者：
Molloy, M [1 ]
Reed, B
机构：
[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada
[2] Univ Paris 06, CNRS, Equipe Combinatoire, Paris, France
来源：
COMBINATORICA | 1998年 / 18卷 / 02期
关键词：
AMS Subject Classification (1991) Classes:  05C15;
D O I：
10.1007/PL00009820
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We prove that the total chromatic number of any graph with maximum degree Delta is at most Delta plus an absolute constant. In particular, we show that for a sufficiently large, the total chromatic number of such a graph is at most Delta+10(26). The proof is probabilistic.
引用
收藏
页码：241 / 280
页数：40
相关论文
共 50 条
  • [41] An upper bound for the chromatic number of line graphs
    King, A. D.
    Reed, B. A.
    Vetta, A.
    EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (08) : 2182 - 2187
  • [42] Total chromatic number of folded hypercubes
    Chen, Meirun
    Guo, Xiaofeng
    Zhai, Shaohui
    ARS COMBINATORIA, 2013, 111 : 265 - 272
  • [43] The history of the total chromatic number conjecture
    Shahmohamad, H., 1600, Charles Babbage Research Centre (86):
  • [44] Snarks with total chromatic number 5
    Vakgroep Toegepaste Wiskunde en Informatica, Universiteit Gent, Belgium
    不详
    不详
    Discrete Math. Theor. Comput. Sci., 1 (369-382):
  • [45] TOTAL DOMINATOR CHROMATIC NUMBER OF A GRAPH
    Kazemi, Adel P.
    TRANSACTIONS ON COMBINATORICS, 2015, 4 (02) : 57 - 68
  • [46] THE TOTAL CHROMATIC NUMBER OF SOME GRAPHS
    张忠辅
    张建勋
    王建方
    ScienceinChina,SerA., 1988, Ser.A.1988 (12) : 1434 - 1441
  • [47] THE TOTAL CHROMATIC NUMBER OF SOME GRAPHS
    ZHANG, ZF
    ZHANG, JX
    WANG, JF
    SCIENTIA SINICA SERIES A-MATHEMATICAL PHYSICAL ASTRONOMICAL & TECHNICAL SCIENCES, 1988, 31 (12): : 1434 - 1441
  • [48] Snarks with total chromatic number 5
    Brinkmann, Gunnar
    Preissmann, Myriam
    Sasaki, Diana
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2015, 17 (01): : 369 - 382
  • [49] THE TOTAL CHROMATIC NUMBER OF SOME GRAPHS
    张忠辅
    张建勋
    王建方
    Science China Mathematics, 1988, (12) : 1434 - 1441
  • [50] RECENT RESULTS ON THE TOTAL CHROMATIC NUMBER
    HILTON, AJW
    DISCRETE MATHEMATICS, 1993, 111 (1-3) : 323 - 331
12345