论文标题
用不包括未成年人的涂色
Coloring hypergraphs with excluded minors
论文作者
论文摘要
Hadwiger的猜想是图理论中最著名的开放问题之一，指出每个不包含$ k_t $作为未成年人的图形都是$（T-1）$ - 可色彩。这项工作的目的是证明Hadwiger问题的自然扩展存在于HyperGraph着色，并得出一些首先的部分结果和应用。我们说，如果可以通过$ H_2 $获得$ H_1 $的超图$ h_2 $，将普通的图形未成年人概括为HyperGraph $ h_1 $是$ H_2 $的少数。我们首先表明，Hadwiger对HyperGraphs的猜想的延伸较弱：每$ T \ ge 1 $，都会存在一个有限的（最小）整数$ h（t）$，因此每个无$ k_t $ -minor is $ h（t）$ $ h（t）$ - $$ \ left \ lceil \ frac {3} {2} {2}（t-1）\ right \ rceil \ le h（t）\ le 2g（t）$ $，其中$ g（t）$表示最大的图形数，没有$ k_t $ -minor。使用Delcourt和Postle的最新结果，即$ g（t）= O（t \ log \ log t）$，这会产生$ h（t）= o（t \ log \ log t）$。我们进一步猜测，$ h（t）= \ left \ lceil \ frac {3} {2}（t-1）\ right \ rceil $，即，每个hypergraph no $ k_t $ -minor is $ \ \ weft \ weft \ lew \ lew \ lceil \ frac \ frac {3} {3} {3} {3} {2} {2} {2} {2} {2} {2} {2} {2}（ 1 $，并证明所有具有独立号码的超图的猜想最多为$ 2 $。通过考虑特殊类别的超图，以上还具有一些有趣的普通图色应用程序，例如： - 色数的图$ c k t \ log \ log t $包含$ k_t $ -minors，带有$ k $ - 边缘连接的分支机构， - 色数的图$ c q t \ log \ log t $包含$ k_t $ -minors，带有modulo- $ q $ - 连接的分支集， - 考虑到挖掘的循环超图，我们在大型二分法数中恢复了强大的未成年人的已知结果，作为特殊情况。
Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain $K_t$ 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 $H_1$ is a minor of a hypergraph $H_2$, if a hypergraph isomorphic to $H_1$ can be obtained from $H_2$ via a finite sequence of vertex- and hyperedge-deletions, and hyperedge contractions. We first show that a weak extension of Hadwiger's conjecture to hypergraphs holds true: For every $t \ge 1$, there exists a finite (smallest) integer $h(t)$ such that every hypergraph with no $K_t$-minor is $h(t)$-colorable, and we prove $$\left\lceil\frac{3}{2}(t-1)\right\rceil \le h(t) \le 2g(t)$$ where $g(t)$ denotes the maximum chromatic number of graphs with no $K_t$-minor. Using the recent result by Delcourt and Postle that $g(t)=O(t \log \log t)$, this yields $h(t)=O(t \log \log t)$. We further conjecture that $h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil$, i.e., that every hypergraph with no $K_t$-minor is $\left\lceil\frac{3}{2}(t-1)\right\rceil$-colorable for all $t \ge 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: -graphs of chromatic number $C k t \log \log t$ contain $K_t$-minors with $k$-edge-connected branch-sets, -graphs of chromatic number $C q t \log \log t$ contain $K_t$-minors with modulo-$q$-connected branch sets, -by considering cycle hypergraphs of digraphs we recover known results on strong minors in digraphs of large dichromatic number as special cases.
