























We start by building up some theory to state Wagner's Theorem, and then prove it using Kuratowski's Theorem, a proof of which is found in Diester (2000). Following this, we establish some connections between the chromatic number of a graph and some of its forbidden minors. The idea is that if we forbid $G$ to have certain graphs as a minor, then the chromatic number of $G$ cannot be too large. Intuitively, this makes sense: if we disallow $G$ from having too many edges, then this makes it easier to colour the graph with fewer colours; we will of course make this precise. We close by explaining how this all relates to Hadwiger's Conjecture.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。