Vertex Colouring and Forbidden Subgraphs – A Survey
Vertex Colouring and Forbidden Subgraphs – A Survey
复制标题
DOI：
10.1007/s00373-003-0540-1
复制
发表时间：
2004-03
影响因子：
0.7
通讯作者：
B. Randerath;I. Schiermeyer
中科院分区：
文献类型：
--
作者：
B. Randerath;I. Schiermeyer
文献中有各种各样的着色概念和结果。这里我们的重点是调查根据禁止诱导子图条件定义的图的顶点着色结果。因此，希望从问题的图着色公式中获得有用结果的人必须做的不仅仅是表明该问题相当于图着色的一般问题。如果还有希望，还必须获得有关需要着色的图的结构的信息（D.S. Johnson [66]）。
There is a great variety of colouring concepts and results in the literature. Here our focus is to survey results on vertex colourings of graphs defined in terms of forbidden induced subgraph conditions.Thus, one who wishes to obtain useful results from a graph coloring formulation of his problem must do more than just show that the problem is equivalent to the general problem of coloring a graph. If there is to be any hope, one must also obtain information about the structure of the graphs that need to be colored (D.S. Johnson [66]).