
Re: A New Graph Coloring Conjecture.
Posted:
Jun 18, 2013 6:57 PM


On Tuesday, June 18, 2013 3:14:41 PM UTC7, bill wrote: > Conjecture: A graph is fourcolorable, if it does not contain a complete K5 sub graph.
Sorry, post not entirely true. We have
Kuratowski's theorem:
A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). A subdivision of a graph results from inserting vertices into edges (for example, changing an edge ???? to ?????) zero or more times.
So replace "K3,3 subgraph" with "subgraph that is a K3,3 subdivision".
Also, we need the graph to free of subgraphs that are K5 subdivisions.
ZG

