Coloring and Labeling Problems on Graphs
Daniel W. Cranston · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2007
This thesis studies both several extremal problems about coloring of graphs and a labeling problem on graphs. We consider colorings of graphs that are either embeddable in the plane or have low maximum degree. We consider three problems: coloring the vertices of a graph so that no adjacent vertices receive the same color, coloring the edges of a graph so that no adjacent edges receive the same color, and coloring the edges of a graph so that neither adjacent edges nor edges at distance one receive the same color. We use the model where colors on vertices must be chosen from assigned lists and consider the minimum size of lists needed to guarantee the existence of a proper coloring. More precisely, a list assignment function L assigns to each vertex a list of colors. A proper L-coloring is a proper coloring such that each vertex receives a color from its list. A graph is k-list-colorable if it has an L-coloring for every list assignment L that assigns each vertex a list of size k. The list chromatic number χl(G) of a graph G is the minimum k such that G is k-list-colorable. We also call the list chromatic number the choice number of the graph. If a graph is k-list-colorable, we call it k-choosable. The elements of a graph are its vertices and edges. A proper total coloring of a graph is a coloring