Weak diameter choosability of graphs with an excluded minor

Abstract

Weak diameter coloring of graphs recently attracted attention partially due to its connection to asymptotic dimension of metric spaces. We consider weak diameter list-coloring of graphs in this paper. Dvořák and Norin proved that graphs with bounded Euler genus are 3-choosable with bounded weak diameter. In this paper, we extend their result by showing that for every graph $H$, $H$-minor free graphs are 3-choosable with bounded weak diameter. The upper bound 3 is optimal and it strengthens an earlier result for non-list-coloring $H$-minor free graphs with bounded weak diameter. As a corollary, $H$-minor free graphs with bounded maximum degree are 3-choosable with bounded clustering, strengthening an earlier result for non-list-coloring. When $H$ is planar, we prove a much stronger result: for every 2-list-assignment $L$ of an $H$-minor free graph, every precoloring with bounded weak diameter can be extended to an $L$-coloring with bounded weak diameter. As a corollary, for any planar graph $H$ and $H$-minor free graph $G$, there are exponentially many list-colorings of $G$ with bounded weak diameter (and with bounded clustering if $G$ also has bounded maximum degree); and every graph with bounded layered tree-width and bounded maximum degree has exponentially many 3-colorings with bounded clustering. We also show that the aforementioned results for list-coloring cannot be extended to odd minor free graphs by showing that some bipartite graphs with maximum degree $\Delta$ are $k$-choosable with bounded weak diameter only when $k=\Omega (\log \Delta /\log \log \Delta )$. On the other hand, we show that odd $H$-minor graphs are 3-colorable with bounded weak diameter, implying an earlier result about clustered coloring of odd $H$-minor free graphs with bounded maximum degree.

References in corpus (9)

• Layered Separators in Minor-Closed Graph Classes with Applications
• Coloring planar graphs with three colors and no large monochromatic components
• Clustered 3-Colouring Graphs of Bounded Degree
• Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Assouad-Nagata dimension of minor-closed metrics