Files in this item



application/pdfColoring and Labeling Problems on Graphs.pdf (496kB)
(no description provided)PDF


Title:Coloring and Labeling Problems on Graphs
Author(s):Cranston, Daniel W.
Abstract: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 \textit{list assignment function} L assigns to each vertex a list of colors. A \textit{proper L-coloring} is a proper coloring such that each vertex receives a color from its list. A graph is \textit{k-list-colorable} if it has an L-coloring for every list assignment L that assigns each vertex a list of size k. The \textit{list chromatic number} \chi_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 \textit{choice number} of the graph. If a graph is k-list-colorable, we call it \textit{k-choosable}. The \textit{elements} of a graph are its vertices and edges. A \textit{proper total coloring} of a graph is a coloring of the elements so that no adjacent elements and no incident elements receive the same color. The \textit{total list-chromatic number} is the minimum list size that guarantees the existence of a proper total coloring. We give a linear-time algorithm to find a proper total coloring from lists of size 2\Delta(G)-1. When \Delta(G)=4, our algorithm improves the best known upper bound. When \Delta(G)\in\{5,6\} our algorithm matches the best known upper bound and runs faster than the best previously known algorithm. The \textit{square} of a graph G is the graph obtained from G by adding the edge xy whenever the distance between x and y in G is 2. We study the list chromatic numbers of squares of subcubic graphs; a graph is \textit{subcubic} if it has maximum degree at most 3. We show that the square of every subcubic graph other than the Petersen graph is 8-list-colorable. For planar graphs with large girth, we use the discharging method to improve this upper bound. We show that the square of a planar subcubic graph with girth at least 7 is 7-list-colorable. We show that the square of a planar subcubic graph with girth at least 9 is 6-list-colorable. In each case we give linear-time algorithms to construct the colorings from the assigned lists. The \textit{strong edge-chromatic number} of a graph is the minimum number of colors needed to color the edges so that no two edges on a path of length at most 3 receive the same color. Erd\H{o}s and Ne\'{s}etril conjectured that when \Delta(G)=4, the strong edge-chromatic number is at most 20; they gave a construction requiring 20 colors. The previous upper bound was 23, due to Horak. We improve this upper bound to 22. We study the list edge-chromatic numbers of planar graphs. A graph is \textit{k-edge-choosable}, if its line graph L(G) is k-choosable. We call the choice number of the line graph L(G) the \textit{edge choice number} of G. A \textit{kite} is the union of two 3-cycles that share an edge. We show that if a planar graph has no kite (as a subgraph) and has maximum degree at least 9, then its list edge-chromatic number equals its maximum degree. We also show that if a planar graph has no kite (as a subgraph) and has maximum degree at least 6, then the list edge-chromatic number is at most one more than the maximum degree; the optimal bound is at most one less than this. A graph is \textit{(r,s)-choosable} if whenever each vertex is given a list of r colors, we can choose a sublist of s colors for each vertex so that adjacent vertices receive disjoint sublists. A graph is G \textit{(r,s)-edge-choosable} if its line graph L(G) is (r,s)-choosable. Mohar conjectured that all 3-regular graphs are (7,2)-edge-choosable. If true, this result would be tight. We show that all 3-edge-colorable graphs are (7,2)-edge-choosable; in addition, we show that many snarks are (7,2)-edge-choosable. In each case, we give a linear-time algorithm to construct the coloring from given lists. The \textit{sum choice number} of a graph is the minimum total weight of a positive integer valuation of its vertices such that the graph is L-colorable for any list assignment L that the size of the list for each vertex is the integer value given to that vertex. We generalize this idea to the \textit{k-sum choice number}, which is the minimum sum of list sizes such that we can choose k colors for each vertex (from its list) so that the sets of colors assigned to adjacent vertices are disjoint. We determine the 2-sum choice number of paths and cycles; additionally we determine all list-size assignment functions that achieve the 2-sum choice number for paths and cycles. A \textit{labeling} of a graph is a bijective function from the set \{1,2,\ldots,|E|\} onto the edges of the graph. The sum of the labels on edges incident to a vertex v is the \textit{vertex-sum} at v. A labeling is \textit{antimagic} if the vertex-sums are distinct. Ringel~\cite{hartsfield} conjectured that every connected graph other than K_2 has an antimagic labeling. We prove that every regular bipartite graph other than a matching has an antimagic labeling.
Issue Date:2007-10
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2007-2824
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-22

This item appears in the following Collection(s)

Item Statistics