Masters Thesis

Coloring Graphs and Digraphs

A coloring of a (directed or undirected) graph is an assignment of colors to the vertices such that the endpoints of each edge receive different colors. A star coloring of an undirected graph is a coloring such that every path on 4 vertices receives at least 3 colors. An incoloring of a directed graph is a coloring such that a path on 3 vertices in the underlying graph receives two colors only if both of its edges are oriented towards the middle vertex in the path. There is a deep connection between incolorings of directed graphs and star colorings of undirected graphs. In this thesis we investigate how different orientations of graphs impact the number of colors required for an incoloring, and the consequences that this has on star coloring. The results we obtain for grid graphs, prisms, Möbius ladders, and outerplanar triangle-free graphs are best possible.

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.