Colouring Graphs When the Number of Colours is Almost the Maximum Degree ∗
Colouring Graphs When the Number of Colours is Almost the Maximum Degree ∗
复制标题
当颜色数量接近最大次数时的着色图*
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
B. Reed
中科院分区：
文献类型：
--
作者：
Michael Molloy;B. Reed
我们考虑具有最大度∆的图的色数。对于足够大的∆，我们确定了对(∆+1−k)可色性的障碍必须是局部条件的k的精确值，即小的子图。我们还证明了对于足够大的∆常数，(∆+1−k)-色性要么是NP完全的，要么可以在线性时间内求解，并且我们精确地确定了每种情况对应的k值。AMS主题分类：05C15∗本论文的简短初步版本出现在[23]和[24]的会议记录中。
We consider the chromatic number of graphs with maximum degree ∆. For sufficiently large ∆, we determine the precise values of k for which the barrier to (∆+1−k)colourability must be a local condition, i.e. a small subgraph. We also show that for ∆ constant and sufficiently large, (∆ + 1 − k)-colourability is either NP-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case. AMS Subject Classification: 05C15 ∗Short preliminary versions of this paper appeared in conference proceedings in [23] and [24].