An improved bound for the strong chromatic number

被引：16
|
作者：
Haxell, P. E. [1 ]
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
来源：
JOURNAL OF GRAPH THEORY | 2008年 / 58卷 / 02期
关键词：
strong chromatic number; maximum degree; partition;
D O I：
10.1002/jgt.20300
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let eta > 0 be given. Then there exists d(0) = d(0)(eta) such that the following holds. Let G be a finite graph with maximum degree at most d >= d(0) whose vertex set is partitioned into classes of size alpha d, where alpha >= 11/4 + eta. Then there exists a proper coloring of G with alpha d colors in which each class receives all alpha d colors. (C) 2008 Wiley Periodicals, Inc.
引用
收藏
页码：148 / 158
页数：11
相关论文
共 50 条
  • [1] An asymptotic bound for the strong chromatic number
    Lo, Allan
    Sanhueza-Matamala, Nicolas
    COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (05): : 768 - 776
  • [2] An Improved Bound on the Chromatic Number of the Pancake Graphs
    Konstantinova, Elena
    Droogendijk, Leen
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (01) : 35 - 46
  • [3] Improved upper bound for acyclic chromatic number of graphs
    Cai, Jiansheng
    Wang, Jihui
    Yu, Jiguo
    ARS COMBINATORIA, 2019, 142 : 231 - 237
  • [4] Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs
    Cai, Jian-sheng
    Zhu, Xu-ding
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2018, 34 (04): : 798 - 800
  • [5] Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs
    Jian-sheng Cai
    Xu-ding Zhu
    Acta Mathematicae Applicatae Sinica, English Series, 2018, 34 : 798 - 800
  • [6] Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs
    Jian-sheng CAI
    Xu-ding ZHU
    Acta Mathematicae Applicatae Sinica, 2018, 34 (04) : 798 - 800
  • [7] On the strong chromatic number
    Haxell, PE
    COMBINATORICS PROBABILITY & COMPUTING, 2004, 13 (06): : 857 - 865
  • [8] Improved lower bound for the list chromatic number of graphs with no Kt minor
    Steiner, Raphael
    COMBINATORICS PROBABILITY & COMPUTING, 2022, 31 (06): : 1070 - 1075
  • [9] A bound on the total chromatic number
    Molloy, M
    Reed, B
    COMBINATORICA, 1998, 18 (02) : 241 - 280
  • [10] BOUND FOR CHROMATIC NUMBER OF A GRAPH
    VANNUFFELEN, C
    AMERICAN MATHEMATICAL MONTHLY, 1976, 83 (04): : 265 - 266
12345