trj
Posts:
91
From:
Korea
Registered:
2/23/12


Re: A New Graph Coloring Conjecture.
Posted:
Jun 19, 2013 5:43 AM


> >quasi wrote: > Consider the set of non4colorable graphs such that > every > proper subgraph is 4colorable. Are there only > finitely many > such graphs, up to isomorphism? > > I think it's clear that the two questions above are > equivalent, > and I'm fairly sure that the answer to those question > is no. > > quasi
Indeed, it is a classical theorem of Erd"os that for any natural numbers k and g there is a nonkcolorable graph in which every cycle has length at least g. E.g. check the wikipedia page on "Girth (graph theory)". If you suppose there is a finite collection of "forbidden" subgraphs for kcoloring, then let g be larger than the largest girth of the elements of the collection, and you would have that there exists another forbidden subgraph outside the collection.

