New upper bounds for the chromatic number of a graph

被引：0

作者：

Stacho, L ^{[1
]}

机构：

[1] Slovak Acad Sci, Inst Math, Dept Informat, Bratislava 84000 4, Slovakia

来源：

JOURNAL OF GRAPH THEORY | 2001年 / 36卷 / 02期

关键词：

simple graph; chromatic number; degree of a vertex;

D O I：

10.1002/1097-0118(200102)36:2<117::AID-JGT6>3.0.CO;2-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that for any graph G, the chromatic number chi (G) less than or equal to Delta (2)(G) + 1, where Delta (2)(G) is the largest degree that a vertex nu can have subject to the condition that nu is adjacent to a vertex whose degree is at least as big as its own, Moreover, we show that the upper bound is best possible in the the following sense: If Delta (2)(G) greater than or equal to 3, then to determine whether chi (G) less than or equal to Delta (2)(G) is an NP-complete problem. (C) 2001 John Wiley & Sons, Inc.

引用

页码：117 / 120

页数：4

共 50 条

[31] Some bounds on the injective chromatic number of graphs
Doyon, Alain
Hahn, Gena
Raspaud, Andre
DISCRETE MATHEMATICS, 2010, 310 (03) : 585 - 590
[32] Bounds for the chromatic number of graphs with partial information
Coffman, WC
Hakimi, SL
Schmeichel, E
DISCRETE MATHEMATICS, 2003, 263 (1-3) : 47 - 59
[33] On Graph Having Clique Number α,Chromatic Number α+1
Xu Baogang(Dept.Math.Shandong University
数学研究与评论, 1991, (03) : 400 - 400
[34] A lower bound for the chromatic capacity in terms of the chromatic number of a graph
Zhou, Bing
DISCRETE MATHEMATICS, 2013, 313 (20) : 2146 - 2149
[35] New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
Wocjan, Pawel
Elphick, Clive
ELECTRONIC JOURNAL OF COMBINATORICS, 2013, 20 (03):
[36] A bound on the chromatic number of the square of a planar graph
Molloy, M
Salavatipour, MR
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) : 189 - 213
[37] A Bound on the Chromatic Number of an Almost Planar Graph
Nenashev G.V.
Journal of Mathematical Sciences, 2014, 196 (6) : 784 - 790
[38] The Chromatic Number of the Disjointness Graph of the Double Chain
Fabila-Monroy, Ruy
Hidalgo-Toscano, Carlos
Leanos, Jesus
Lomeli-Haro, Mario
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2020, 22 (01):
[39] A note on the chromatic number of a dense random graph
Panagiotou, Konstantinos
Steger, Angelika
DISCRETE MATHEMATICS, 2009, 309 (10) : 3420 - 3423
[40] On lower bounds for the chromatic number in terms of vertex degree
Zaker, Manouchehr
DISCRETE MATHEMATICS, 2011, 311 (14) : 1365 - 1370

← 1 2 3 4 5 →