Timeline for Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2016 at 8:29 | comment | added | Gordon Royle | For the $K_6$ example, what happens is that all the "other terms" are identically zero. This is because all the minors involved are obtained by contracting exactly 2 of the $k$ edges (and deleting some of the others) and when the 2 edges lie in a triangle, then this creates a loop and hence an identically zero chromatic polynomial. This can cause a problem only when EVERY pair of the $k$ edges lies in a triangle, which can only occur when the $k$ edges lie in a $k+1$-clique. | |
| Apr 17, 2016 at 8:17 | comment | added | Gordon Royle | Oxley works with cocircuits, while Woodall/Thomassen each work with sets of edges incident with a vertex. So sometimes Oxley can find a cocircuit strictly smaller than any vertex-star and thereby get a smaller $k$ in the first term. This can make a difference, but only for certain contrived examples. | |
| Apr 16, 2016 at 22:27 | comment | added | Fedor Petrov | Also I do not understand why this approach does not prove that $K_6$ is 5-colorable: it has a vertex of degree 5 and all proper minors are 5-colorable. | |
| Apr 16, 2016 at 7:02 | comment | added | Fedor Petrov | If cocircuit is defined as inclusion-minimal codependent set, then in general set of edges incident with a vertex is not a cocircuit (well, it is always a disjoint union of cocircuits). | |
| Apr 15, 2016 at 23:11 | comment | added | Gordon Royle | @Fedor - removing (deleting and contracting) the edges incident with a vertex in a graph corresponds to removing the elements of a cocircuit in a matroid. In a graph, the edges incident with a vertex are a special type of cocircuit, so the matroid formulation latter is slightly more general even when the matroid is graphic. | |
| Apr 15, 2016 at 18:08 | comment | added | Fedor Petrov | I do not understand the formulation of Oxley's result for matroids. What does it mean 'remove a vertex'? | |
| May 12, 2015 at 5:28 | vote | accept | user19906 | ||
| May 11, 2015 at 14:05 | history | edited | Gordon Royle | CC BY-SA 3.0 |
Added more info regarding BL paper
|
| May 11, 2015 at 12:13 | history | answered | Gordon Royle | CC BY-SA 3.0 |