Eylem Seç
On the List Coloring Problem and Its Equitable Variants
Başlık:
On the List Coloring Problem and Its Equitable Variants
Yazar:
Mudrock, Jeffrey Allen, author.
ISBN:
9780438124493
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (205 pages)
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
Advisors: Hemanshu Kaul Committee members: Gruia Calinescu; Robert B. Ellis; Michael J. Pelsmajer.
Özet:
In this thesis we study list coloring which was introduced independently by Vizing and Erdos, Rubin, and Taylor in the 1970's. Suppose we associate a list assignment L with a graph G which assigns a list, L(v), of colors to each v ∈ V(G). A proper L-coloring of G, f, is a proper coloring such that f(v) ∈ L(v) for each v ∈ V(G).
The list chromatic number of the Cartesian product of graphs is not well understood. The best result is by Borowiecki, Jendrol, Kral, and Miskuf (2006) who proved that the list chromatic number of the Cartesian product of two graphs can be bounded in terms of the list chromatic number and the coloring number of the factors. In Chapter 2, we use the Alon-Tarsi Theorem and an extension of it discovered by Schauz in 2010 to find improved bounds on the list chromatic number and paint number (i.e. online list chromatic number) of the Cartesian product of an odd cycle or complete graph with a traceable graph. We also identify certain Cartesian products as chromatic-choosable.
In Chapter 3, we generalize the notion of strong critical graphs, introduced by Stiebitz, Tuza, and Voigt in 2008, to strong k-chromatic-choosable graphs, and we show that it gives a strictly larger family of graphs that includes odd cycles, cliques, the join of a clique and any strongly chromatic-choosable graph, and many more families of graphs. We prove sharp bounds on the list chromatic number of certain Cartesian products where one factor is a strong k-chromatic-choosable graph satisfying an edge bound. Our proofs rely on the notion of unique-choosability as a sufficient condition for list colorability and the list color function which is a list analogue of the chromatic polynomial.
In Chapter 4, we study a list analogue of equitable coloring introduced by Kostochka, Pelsmajer, and West in 2003. A graph G is said to be equitably k-choosable if it has a proper L -coloring that uses no color more than
In Chapter 5, we introduce a new list analogue of equitable coloring: proportional choosability. For this new notion, the number of times a color is used must be proportional to the number of lists in which the color appears. Proportional k-choosability implies both equitable k-choosability and equitable k-colorability. Also, the graph property of being proportionally k-choosable is monotone, and if a graph is proportionally k-choosable, it must be proportionally (k+1)-choosable. We study the proportional choosability of graphs with small order and disconnected graphs, and we completely characterize proportionally 2-choosable graphs.
Notlar:
School code: 0091
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(690851.1) | 690851-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.