Semester
Summer
Date of Graduation
2000
Document Type
Thesis
Degree Type
MS
College
Statler College of Engineering and Mineral Resources
Department
Lane Department of Computer Science and Electrical Engineering
Committee Chair
Elaine Eschen.
Abstract
Let G = (V, E) be a simple graph. The clique hypergraph of G, denoted as CH( G), has V as its set of vertices, and the maximal cliques as its hyperedges. Let Sk be a set of k colors. A map c : V Sk is a proper k-coloring for CH(G) if any maximal clique of G with at least two vertices receives at least two distinct colors. Let W ⊂ V, and let s ≥ 1. We say that G is (W, s)-extendible if any assignment on W with at most s colors can be extended to a proper s-coloring of CH(G). We prove that the clique hypergraphs of chordal and comparability graphs are bicolorable and that the clique hypergraphs of circular-arc graphs are 3-colorable. Our main result is the characterization of (W, 2)-extendibility for chordal graphs in the case when W=2 .
Recommended Citation
Poon, Hoifung, "Coloring clique hypergraphs" (2000). Graduate Theses, Dissertations, and Problem Reports. 1008.
https://researchrepository.wvu.edu/etd/1008