Coloring hypergraphs with excluded minors

Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain Kt as a minor is properly (t−1)-colorable. The purpose of this work is to demonstrate that a natural extension of Hadwiger's problem to hypergraph coloring exists, and to derive some first partial results and applications. Generalizing ordinary graph minors to hypergraphs, we say that a hypergraph H1 is a minor of a hypergraph H2, if a hypergraph isomorphic to H1 can be obtained from H2 via a finite sequence of the following operations: • deleting vertices and hyperedges, • contracting a hyperedge (i.e., merging the vertices of the hyperedge into a single vertex). First we show that a weak extension of Hadwiger's conjecture to hypergraphs holds true: For every t≥1, there exists a finite (smallest) integer h(t) such that every hypergraph with no Kt-minor is h(t)-colorable, and we prove 32(t−1)≤h(t)≤2g(t) where g(t) denotes the maximum chromatic number of graphs with no Kt-minor. Using the recent result by Delcourt and Postle that g(t)=O(tloglogt), this yields h(t)=O(tloglogt). We further conjecture that h(t)=32(t−1), i.e., that every hypergraph with no Kt-minor is 32(t−1)-colorable for all t≥1, and prove this conjecture for all hypergraphs with independence number at most 2. By considering special classes of hypergraphs, the above additionally has some interesting applications for ordinary graph coloring, such as: • every graph G is O(ktloglogt)-colorable or contains a Kt-minor model all whose branch-sets are k-edge-connected, • every graph G is O(qtloglogt)-colorable or contains a Kt-minor model all whose branch-sets are modulo-q-connected (i.e., every pair of vertices in the same branch-set has a connecting path of prescribed length modulo q), • by considering cycle hypergraphs of digraphs, we obtain known results on strong minors in digraphs with large dichromatic number as special cases. We also construct digraphs with dichromatic number 32(t−1) not containing the complete digraph on t vertices as a strong minor, thus answering a question by Mészáros and the author in the negative.