Eylem Seç
Graph Homomorphisms and Vector Colorings
Başlık:
Graph Homomorphisms and Vector Colorings
Yazar:
Levet, Michael Robert, author.
ISBN:
9780438112711
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (58 pages)
Genel Not:
Source: Masters Abstracts International, Volume: 57-06M(E).
Advisors: Linyuan Lu Committee members: Eva Czabarka.
Özet:
A graph vertex coloring is an assignment of labels, which are referred to as colors, such that no two adjacent vertices receive the same color. The vertex coloring problem is NP-Complete [8], and so no polynomial time algorithm is believed to exist. The notion of a graph vector coloring was introduced as an efficiently computable relaxation to the graph vertex coloring problem [7]. In [6], the authors examined the highly symmetric class of 1-walk regular graphs, characterizing when such graphs admit unique vector colorings. We present this characterization, as well as several important consequences discussed in [5, 6]. By appealing to this characterization, several important families of graphs, including Kneser graphs, Quantum Kneser graphs, and Hamming graphs, are shown to be uniquely vector colorable. Next, a relationship between locally injective vector colorings and cores is examined, providing a sufficient condition for a graph to be a core. As an immediate corollary, Kneser graphs, Quantum Kneser graphs, and Hamming graphs are shown to be cores. We conclude by presenting a characterization for the existence of a graph homomorphism between Kneser graphs having the same vector chromatic number. The necessary condition easily generalizes to Quantum Kneser graphs, simply by replacing combinatorial expressions with their quantum analogues.
Notlar:
School code: 0202
Konu Başlığı:
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(689406.1) | 689406-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.