Cycle lengths and chromatic number of graphs

被引：17
|
作者：
Mihók, P
Schiermeyer, I
机构：
[1] Tech Univ, Fac Econ, Kosice 04001, Slovakia
[2] Slovak Acad Sci, Math Inst, Kosice 04001, Slovakia
[3] Tech Univ Bergakad Freiberg, Inst Diskrete Math & Algebra, D-09596 Freiberg, Germany
来源：
DISCRETE MATHEMATICS | 2004年 / 286卷 / 1-2期
关键词：
chromatic number; cycle length; k-degenerate graph;
D O I：
10.1016/j.disc.2003.11.055
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
For a simple finite graph G let C-o(G) and C-e(G) denote the set of odd cycle lengths and even cycle lengths in a graph G, respectively. We will show that the chromatic number chi(G) of G satisfies: chi(G) less than or equal to min {2r + 2,2s + 3} less than or equal to r + s + 2, if \Co(G)\ = r and \Ce(G)\ = s. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：147 / 149
页数：3
相关论文
共 50 条
  • [41] Chromatic Number and Orientations of Graphs and Signed Graphs
    Qi, Hao
    Wong, Tsai-Lien
    Zhu, Xuding
    TAIWANESE JOURNAL OF MATHEMATICS, 2019, 23 (04): : 767 - 776
  • [42] THE CHROMATIC POLYNOMIAL FOR CYCLE GRAPHS
    Lee, Jonghyeon
    Shin, Heesung
    KOREAN JOURNAL OF MATHEMATICS, 2019, 27 (02): : 525 - 534
  • [43] ON GRAPHS WITH MAXIMUM DIFFERENCE BETWEEN GAME CHROMATIC NUMBER AND CHROMATIC NUMBER
    Hollom, Lawrence
    arXiv, 2023,
  • [44] SUBGRAPHS OF LARGE CONNECTIVITY AND CHROMATIC NUMBER IN GRAPHS OF LARGE CHROMATIC NUMBER
    ALON, N
    KLEITMAN, D
    THOMASSEN, C
    SAKS, M
    SEYMOUR, P
    JOURNAL OF GRAPH THEORY, 1987, 11 (03) : 367 - 371
  • [45] On graphs with maximum difference between game chromatic number and chromatic number
    Hollom, Lawrence
    DISCRETE MATHEMATICS, 2025, 348 (02)
  • [46] STABILITY NUMBER AND CHROMATIC NUMBER OF TOLERANCE GRAPHS
    NARASIMHAN, G
    MANBER, R
    DISCRETE APPLIED MATHEMATICS, 1992, 36 (01) : 47 - 56
  • [47] ON THE DISTRIBUTION OF CYCLE LENGTHS IN GRAPHS
    GYARFAS, A
    KOMLOS, J
    SZEMEREDI, E
    JOURNAL OF GRAPH THEORY, 1984, 8 (04) : 441 - 462
  • [48] Cycle lengths in planar graphs
    Verstraëte, J
    UTILITAS MATHEMATICA, 2006, 69 : 109 - 117
  • [49] A note on cycle lengths in graphs
    Gould, RJ
    Haxell, PE
    Scott, AD
    GRAPHS AND COMBINATORICS, 2002, 18 (03) : 491 - 498
  • [50] Distribution of cycle lengths in graphs
    Fan, GH
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) : 187 - 202
12345