AI enables tighter bound on chromatic number in graph theory
Tweaking the constant in the Linear Hadwiger Theorem
Discrete Mathematics
Summary
In graph theory, a major question is how many colors you need to color a graph without overlapping colors on connected points. A recent proof showed there's a constant connecting this number to a graph’s Hadwiger number but with an extremely large constant. The authors use artificial intelligence to reduce that huge constant to a much smaller, more practical number. This means the coloring rules can be better understood and applied using improved bounds.
What this means in practice
- •For graph algorithm developers: Use improved bounds on graph coloring complexity to optimize algorithms that assign resources without conflicts based on graph structure.
- •For computational complexity engineers: Incorporate tighter theoretical limits on chromatic number in the design and analysis of complexity-constrained computing systems.
A theory result. No direct application yet.
Authors
David R. Wood
Abstract
Norin and Steiner recently proved the Linear Hadwiger Conjecture. That is, there is an absolute constant $C$ such that every graph $G$ satisfies $χ(G)\leqslant C\,\text{had}(G)$, where $χ(G)$ is the chromatic number and $\text{had}(G)$ is the Hadwiger number of $G$. Their proof gives a non-optimised constant $C$ of order $10^{100}$. This paper uses extensive AI-based optimisation to show that every graph $G$ satisfies $χ(G) \leqslant 19{,}885{,}160\,\text{had}(G)$.