Tight Minimum Degree Conditions for Apex‐Outerplanar Minors and Subdivisions in Graphs and Digraphs

ABSTRACT Motivated by Hadwiger's conjecture and related problems for list‐coloring, we study graphs for which every graph with minimum degree at least contains as a minor. We prove that a large class of apex‐outerplanar graphs satisfies this property. Our result gives the first examples of such graphs whose vertex cover numbers are significantly larger than half the number of its vertices, which breaks a barrier for attacking related coloring problems via extremal functions, and recovers all known such graphs that have arbitrarily large maximum degree. Our proof can be adapted to directed graphs to show that if is the digraph obtained from a directed cycle or an in‐arborescence by adding an apex source, then every digraph with minimum out‐degree contains as a subdivision or a butterfly minor respectively. These results provide the optimal upper bound for the chromatic number and dichromatic number of graphs and digraphs that do not contain the aforementioned graphs or digraphs as a minor, butterfly minor and a subdivision, respectively. Special cases of our results solve an open problem of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé and strengthen results of Gishboliner, Steiner and Szabó.