> >quasi wrote: > Consider the set of non-4-colorable graphs such that > every > proper subgraph is 4-colorable. 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 non-k-colorable 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 k-coloring, 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.