Dominating Kt ${K}_{t}$‐Models

ABSTRACT

A dominating ‐model in a graph is a sequence of pairwise disjoint non‐empty connected subgraphs of , such that for every vertex in has a neighbour in . Replacing ‘every vertex in ’ by ‘some vertex in ’ retrieves the standard definition of ‐model, which is equivalent to being a minor of . We explore in what sense dominating ‐models behave like (non‐dominating) ‐models. The two notions are equivalent for but are already very different for , since the 1‐subdivision of any graph has no dominating ‐model. Nevertheless, we show that every graph with no dominating ‐model is 2‐degenerate and 3‐colourable. More generally, we prove that every graph with no dominating ‐model is ‐colourable. Motivated by the connection to chromatic number, we study the maximum average degree of graphs with no dominating ‐model. We give an upper bound of and show that random graphs provide a lower bound of , which we conjecture is asymptotically tight. This result is in contrast to the ‐minor‐free setting, where the maximum average degree is . A natural strengthening of Hadwiger's conjecture arises: Is every graph with no dominating ‐model ‐colourable? We provide two pieces of evidence for this: (1) It is true for almost every graph. (2) Every graph with no dominating ‐model has a ‐colourable induced subgraph on at least half the vertices, which implies there is an independent set of size at least .