Coloring and labeling problems on graphs

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 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 choice number of the graph. If a graph is k-list-colorable, we call it k-cooosable.;The elements of a graph are its vertices and edges. A 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 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 2Delta( G) - 1. When Delta(G) = 4, our algorithm improves the best known upper bound. When Delta(G) ∈ {5, 6} our algorithm matches the best known upper bound and runs faster than the best previously known algorithm.;The 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 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 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ős and Nesetril 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 k-edge-choosable, if its line graph L(G ) is k-choosable. We call the choice number of the line graph L(G) the edge choice number of G. A 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 (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 (r,s)- edge-choosable if its line graph L( G) is (r, s)-choosable. Mohar [37] 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 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 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 labeling of a graph is a bijective function from the set {1,2,...,|E|} onto the edges of the graph. The sum of the labels on edges incident to a vertex v is the vertex-sum at v. A labeling is antimagic if the vertex-sums are distinct. Ringel [19] conjectured that every connected graph other than K2 has an antimagic labeling. We prove that every regular bipartite graph other than a matching has an antimagic labeling.