The main focus of this paper is exploring precoloring extensions problems, specifically when the precolored subgraph consists of cliques. We explore this topic by providing more details to a proof by Michael O. Albertson in the paper ‘You Can’t Paint Yourself into a Corner’. Albertson shows that for a graph with chromatic number and ⊂ (), if induces a set of cliques such that each clique is of order and whose pairwise distance is at least 6 − 2, then any proper ( + 1) - coloring of can be extended to a proper ( + 1) - coloring of . Before considering this theorem, we provide background on precoloring extensions, touch upon list-colorings and their relation to precoloring extensions, and discuss an important proof technique involving Kempe chains that we use throughout the paper. We also provide a result by Alexandr Kostochka, which is actually an improvement to Albertson’s result mentioned above. Kostochka’s result decreases the pairwise distance needed between cliques of order to only 4. We then provide Albertson and Moore’s more precise result concerning the distance needed between precolored cliques. Finally, building off of the arguments made in Kostochka’s proof, we prove that when the pairwise distance between cliques of order is 2+ 2, any proper ( + 2) - coloring of can be extended to a proper ( + 2 ) - coloring of .

No results found