In 1943, Hadwiger formulated his celebrated conjecture, connecting the chromatic number $\chi(G)$ of a finite, simple, undirected graph with the cardinality of the largest complete minor, $\eta(G)$. The disjoint union of all finite complete graphs shows that Hadwiger's conjecture fails for infinite, but a slightly weaker version is true in these graphs, and open for finite graphs. In this note we generalize that weaker version to hypergraphs and provide a simple, general, and purely set-theoretical formulation of Hadwiger's conjecture.
Hadwiger conjectured in 1943 that every graph with no $K_t$ minor has chromatic number at most $t-1$. Delcourt and Postle proved that every graph with no $K_t$ minor has chromatic number $O(t\log\log t)$. We build on their result to improve this bound to $O(t\log\log\log t)$.
For a graph $G$, let $\alpha(G)$ be the second smallest eigenvalue of the Laplacian matrix of $G$, also known as the algebraic connectivity. Algebraic connectivity plays an important role in characterizing the connectivity of graphs and convergence properties of networks. Kolokolnikov conjectured that among all graphs...
Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of orde...
Lehel's conjecture states that every 2-edge-colouring of K_n admits a partition of its vertex set into two monochromatic cycles. It was proven for sufficiently large n by {\L}uczak, R\"odl, and Szemer\'edi in 1998, later improved by Allen in 2008, and fully resolved by Bessy and Thomass\'e in 2010. In this paper, we co...
Pedro Araújo, Xiao-Chuan Liu, Taísa L. Martins et al.· 0 citations
The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint directed cycles. Despite being posed in 1981, this conjecture remains unresolved for all $k \ge 4$. We prove a relaxation of this conjecture: every digraph $D$ of minimum out-degree a...
S. Bessy, M. Muis, Jean-Sébastien Sereni et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
