A coloring problem related to Konig's Theorem
John Fergas Wilkinson · 1965
A connection is shown between Konig's Theorem on 0-1 matrices and theorems giving sufficient conditions, in terms of certain forbidden subgraphs, for a graph G to have chromatic number equal to the maximum number of vertices in any clique of G. A conjecture is proposed which would, if true, give the best possible such theorem. Three special cases of this conjecture are proved, and Konig's Theorem is shown to be an easy corollary of any one of them.