I've been calling all such sets of vertices sets of boundary points. A graph may have only one set of boundary points, which is the entire set of vertices in the graph, or it may have many sets of boundary points ranging in size from k vertices to the entire graph. Jaap

Concept 2: Every graph of chromatic number k has at least one set of k or more vertices which in all valid colorings of the graph are never colored with less than k colors. This I think is false; consider the pentagon, which has chromatic number 3. [snip] if S = {v1, v2, v3}, [snip] if S = {v1, v2, v4}, [snip] In both cases, you should get a coloring that contradicts Concept 2. I think you missed the bit where Matt said k _or_more_ vertices . D'oh! Yes, I missed that part, Matt. Of course, as jaapsch points out, this makes Concept 2 trivial and probably not what he had in mind. (The only set that works for the pentagon is the whole vertex set.) At least I covered myself by saying I think 8-). So what he's really getting at is minimal k-chromatic graphs; if G is k-chromatic, he wants to find a subgraph H that is k-chromatic. ... No, wait ... He's looking for a set of vertices S such that if you (properly) color the vertices in S with < k colors, this coloring does not extend to any k-coloring of G.