论文标题
有缺陷的着色非常适合未成年人
Defective coloring is perfect for minors
论文作者
论文摘要
图形类的有缺陷的色度是$ k $，因此存在一个整数$ d $，因此该类中的每个图形都可以分配到最多$ k $诱导的子图中，最多最高$ d $。发现有缺陷的色数是一个基本的图形分区问题，最近由于哈德威格（Hadwiger）对少量关闭家庭着色的猜想而受到了部分关注。在本文中，我们证明，任何次要封闭家庭的有缺陷的色数等于通过标准结构获得的简单下限，证实了Ossona de Mendez，Oum和Wood的猜想。该结果为无限图提供了不可避免的有限未定的无限图表的最佳列表，这些图形无法将其划分为固定数量的诱导子图，并具有均匀界限的最大程度。作为关于聚集着色的推论，我们获得了任何次要家族的聚类的色数与其禁止未成年人的树深度之间的线性关系，改善了诺林，斯科特，西摩和木材证明的早期指数结合，并确认了他们的推测的平面案例。
The defective chromatic number of a graph class is the infimum $k$ such that there exists an integer $d$ such that every graph in this class can be partitioned into at most $k$ induced subgraphs with maximum degree at most $d$. 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.
