\(k\)-Saturated Graphs of Chromatic Number at Least \(k\)

D. Hanson1, B. Toft2
1 University of Regina Regina, Saskatchewan Canada, S4S OA2
2 Odense Universitet Odense, Denmark

Abstract

In this paper, we consider the structure of \(k\)-saturated graphs \((G \not\supset K_k,\) but \(G+e \supset K_{k}\) for all possible edges \(e)\\) having chromatic number at least \(k\).