Precoloring Extensions Involving Cliques and the Pairwise Distance Needed Between Them

Document
Document

<p>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 <em>G</em> with chromatic number <em>r</em> and <em>P</em><strong> </strong>⊂<em> V</em> (<em>G</em>), if <em>P</em> induces a set of cliques such that each clique is of order <em>k ≤ r</em> and whose pairwise distance is at least 6<em>k</em> − 2, then any proper (<em>r</em> + 1) - coloring of <em>P</em> can be extended to a proper (<em>r</em> + 1) - coloring of <em>G</em>. 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 <em>k</em> to only 4<em>k</em>. 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 <em>k</em> is 2<em>k </em>+ 2, any proper (<em>r</em> + 2) - coloring of <em>P</em> can be extended to a proper (<em>r</em> + 2 ) - coloring of <em>G</em>.</p>

    Item Description
    Name(s)
    Thesis advisor: Collins, Karen L.
    Date
    May 01, 2019
    Extent
    79 pages
    Language
    eng
    Genre
    Physical Form
    electronic
    Discipline
    Rights and Use
    In Copyright - Non-Commercial Use Permitted
    Digital Collection
    PID
    ir:2520