Illingworth and Wood recently proposed the Dominating Hadwiger's Conjecture, a strengthening of Hadwiger's Conjecture which asserts that every graph with no dominating $K_t$-model is $(t-1)$-colorable. We prove two relaxations of this conjecture. First, we show that every graph with average degree $Ct (\log t)^2$ contains a dominating $K_t$-model for some absolute constant $C$. This bound improves on the $2^{t-2}$ due to Illingworth and Wood and is within an $O(\log t)$ factor from optimal. Second, we prove that the vertices of every graph with no dominating $K_t$-model can be partitioned into $t-1$ parts such that the subgraph induced by each part has bounded maximum degree.
António Girão, S. Norin, Youri Tamitegama et al.· 0 citations
The first open case of Hadwiger's conjecture states that every $K_7$-minor-free graph is 6-colorable. We prove that this is the case for $K_7^=$-minor-free graphs, where $K_7^=$ denotes the graph obtained from $K_7$ by deleting two independent edges. The proof is based on an independently interesting density result: Every 5-connected $K_7^=$-minor-free graph with $n\ge 6$ vertices has at most $4n-8$ edges.
Asymptotic dimension of metric spaces is a large-scale analog of covering dimension of topological spaces. An intersection graph of a family of sets is the graph whose vertices are the members of the family and whose edges correspond to pairs of members with non-empty intersection. Our first main result connects the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ and the Assouad-Nagata dimension of the ambient metric space containing members of ${\mathcal F}$ under some mild and necessary assumptions. We prove that if ${\mathcal F}$ is a family of subsets of a metric space of Assouad-Nagata dimension $n$ such that every ball of radius $r$ intersects at most $f(r/s)$ pairwise disjoint members of ${\mathcal F}$ of diameter at least $s$ for some function $f$, then the asymptotic dimension of the intersection graph of ${\mathcal F}$ is at most $n+1$. This result is optimal both quantitatively and qualitatively in several senses. As a corollary of this result, the asymptotic dimension of the intersection graph of any family of compact convex sets of bounded aspect ratio in ${\mathbb R}^n$, such as a family of balls in ${\mathbb R}^n$, is at most $n+1$. Our second main result states that the asymptotic dimension of the intersection graph of a family ${\mathcal F}$ of connected closed sets of a connected topological space with connected boundary equals the asymptotic dimension of the intersection graph of the family of the boundary of the sets in ${\mathcal F}$, under a mild condition. In particular, the asymptotic dimension of the intersection graphs of families of spheres in ${\mathbb R}^n$ equals $n$ or $n+1$ when $n \geq 2$.
Chun-Hung Liu, S. Norin· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
