Randomly coloring graphs and coloring random graphs.
Published: 2005
Language: eng
Number of pages: 70
Description: We will study three graph coloring problems. In each case randomness is either in the core of the problem, or is used as a tool.An adjacent vertex distinguishing edge-coloring or an avd-coloring of a simple graph G is a proper edge-coloring of  G such that no pair of adjacent vertices meets the same set of colors. We prove that every graph with maximum degree Delta and with no isolated edges has an avd-coloring with at most Delta + 300 colors, provided that Delta > 1020.We prove that if G is triangle-free and has maximum degree at most 3, then chif(G), the fractional chromatic number of G, is at most 3 -   364 . If G has girth at least k and maximum degree at most 3, then chif(G) &le;  ck, where ck is a decreasing sequence and c15 &ap; 2.66681.In the other two problems we consider cubic graphs. We prove that a random cubic graph almost surely is not homomorphic to a cycle of size 7, or equivalently the circular chromatic number of a random cubic graph is almost surely greater than   73 .
Notes: Thesis (M.Sc.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 44-01, page: 0391.

GERSTEIN MICROTEXT copy on microfiche (1 microfiche)