Defective Coloring is Perfect for Minors
Defective Coloring is Perfect for Minors
复制标题
有缺陷的色彩非常适合未成年人
DOI：
10.1007/s00493-024-00081-8
复制
发表时间：
2024
期刊：
影响因子：
1.1
通讯作者：
Liu, Chun-Hung
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung
一类图的亏色数是指存在一个整数的下确界，使得这类图中的每一个图都能被划分成至多个度最大的导出子图。寻找亏色数是一个基本的图划分问题，最近受到关注，部分是由于Hadwiger关于染色次闭族的猜想。本文证明了任意次闭族的亏色数等于由标准构造法得到的简单下界，从而证实了Ossona de Mendez，Oum和Wood的一个猜想.这一结果提供了不可避免的有限子图的最优列表的无限图，不能被划分成一个固定的有限数量的诱导子图一致有界的最大程度。作为聚类着色的推论，我们得到了任意子闭族的聚类色数与其禁子的树深之间的线性关系，改进了Norin，Scott，Seymour和Wood早先证明的指数界，并证实了他们猜想的平面情形.
The defective chromatic number of a graph class is the infimumksuch that there exists an integerdsuch that every graph in this class can be partitioned into at mostkinduced subgraphs with maximum degree at mostd. Finding the defective chromatic number is a fundamental graph partitioning problem and received attention recently partially due to Hadwiger’s conjecture about coloring minor-closed families. In this paper, we prove that the defective chromatic number of any minor-closed family equals the simple lower bound obtained by the standard construction, confirming a conjecture of Ossona de Mendez, Oum, and Wood. This result provides the optimal list of unavoidable finite minors for infinite graphs that cannot be partitioned into a fixed finite number of induced subgraphs with uniformly bounded maximum degree. As corollaries about clustered coloring, we obtain a linear relation between the clustered chromatic number of any minor-closed family and the tree-depth of its forbidden minors, improving an earlier exponential bound proved by Norin, Scott, Seymour, and Wood and confirming the planar case of their conjecture.
登录
查看更多内容
哈维格猜想的一个亲戚
DOI：
10.1137/141002177
发表时间：
2014
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Katherine Edwards;D. Kang;Jaehoon Kim;Sang;P. Seymour
通讯作者：
P. Seymour
DOI：
10.1016/j.aam.2023.102489
发表时间：
2019-12
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
Chun-Hung Liu;F. Wei
通讯作者：
Chun-Hung Liu;F. Wei
打破无 K 小调着色图的简并障碍
影响因子：
1.7
作者：
S. Norin;Zi
通讯作者：
Zi
DOI：
10.1017/s0305004100061521
发表时间：
1984
影响因子：
0.8
作者：
A. Thomason
通讯作者：
A. Thomason
不包括子图或次要图的图形着色有缺陷
影响因子：
1.1
作者：
P. D. Mendez;Sang;D. Wood
通讯作者：
D. Wood