A Coloring Problem Related to König's Theorem

Author: Wilkinson, John Fergas

Year: 1965

Degree: Dissertation (Ph.D.)

Advisor: Hall, Marshall

Committee Member: Unknown, Unknown

Option: Mathematics; Economics

DOI: 10.7907/N6B0-QM91

Abstract

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.

Files