Timeline for Reasons for which a graph may be not $k$ colorable?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2012 at 13:13 | comment | added | Luke Mathieson | Take a $K_{k}$ and subdivide all the edges. The resulting graph is bipartite and thus two color able, but obviously has the complete graph as a minor. | |
| Nov 22, 2012 at 11:20 | comment | added | Giorgio Camerani | @LukeMathieson: Extremely interesting. Do you have an example of a graph which has a $K_k$ minor and which is $k-1$ colorable? | |
| Nov 22, 2012 at 5:24 | comment | added | Luke Mathieson | The Hadwiger Conjecture though is a necessary condition, but not sufficient, so a graph has chromatic number $k$ iff it has a $K_{k}$ minor and something else. As JeffE points out of course, it's likely that the something else is just because (in the sense that it's not a simple answer). | |
| Nov 22, 2012 at 4:47 | comment | added | William Macrae | The Petersen Graph is a smaller example of the same thing. Both the above and the Petersen Graph have $K_4$ minors, though, which goes back to the above comment about Hadwiger's. | |
| Nov 22, 2012 at 1:06 | history | answered | Luke Mathieson | CC BY-SA 3.0 |