Coloring clique hypergraphs

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 .

Name thesis:degree_name

MS

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Lane Department of Computer Science and Electrical Engineering

Year dc:date.available

2000

Author dc:creator

• Poon, Hoifung

Contributors dc:contributor

• Elaine Eschen.

• Computer science
• Mathematics

Identifier

https://researchrepository.wvu.edu/etd/1008

OAI identifier oai:identifier

oai:researchrepository.wvu.edu:etd-2011