Defective coloring is perfect for minors

DOI10.1007/S00493-024-00081-8arXiv2208.10729MaRDI QIDQ6408539FDOQ6408539

Authors: Chun-Hung Liu 

Publication date: 23 August 2022

Abstract: 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 receives 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.

Recommendations

• Clustered colouring in minor-closed classes
• Defective and clustered graph colouring
• Tree-depth, subgraph coloring and homomorphism bounds
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Defective colouring of graphs excluding a subgraph or minor

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Defective coloring is perfect for minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408539)