Defective Colouring of Graphs Excluding A Subgraph or Minor
Defective Colouring of Graphs Excluding A Subgraph or Minor
复制标题
不包括子图或次要图的图形着色有缺陷
DOI：
10.1007/s00493-018-3733-1
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
P. D. Mendez;Sang;D. Wood
Archdeacon（1987）证明了可嵌入在固定曲面上的图可以是3色的，使得每一个色类导出一个有界最大度的子图。Edwards，Kang，Kim，Oum and Seymour（2015）证明了没有Kt +1-子图的图可以是t-着色的，使得每个色类都导出一个有界最大度的子图。我们证明了一个共同的概括，这些定理与较弱的假设排除子图。这一结果导致了几个图类的新的缺陷着色结果，包括具有线性交叉数的图，具有给定厚度的图（与地球-月球问题相关），具有给定栈数或栈数的图，无链接或knockless可嵌入图，具有给定Colin de Verdière参数的图，以及排除完全二部图作为拓扑子图的图。
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.