On constructive methods in the theory of colour-critical graphs (Q1121899): Difference between revisions

A graph G is k-critical if its chromatic number is k but every subgraph of G has chromatic number less than k. This concept was introduced and developed by Dirac in a series of papers in the 1950's as a method of studying graph coloring theory. This paper is a thorough survey, with useful remarks, of constructive methods for k-critical graphs. The list of references, which contains several misprints, is extensive but not complete. The following statement from the authors' concluding paragraph is particularly interesting. ``The concept of criticality-invented for simplifying graph coloring theory - has given rise to numerous investigations and beautiful theorems. However, at the same time it turned out that criticality is not as incisive a restriction as it had been expected to be...presently it seems to be hopeless to search for satisfactory characterization theorems; in particular this applies to the class of color-critical graphs without vertices of degree k-1, a vast area which is almost unexplored.''