✦ LIBER ✦

Circular perfect graphs

✍ Scribed by Xuding Zhu

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 209 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20050

No coin nor oath required. For personal study only.

✦ Synopsis

For 1 d k, let K k=d be the graph with vertices 0; 1; . . . ; k À 1, in which i $ j if d ji À jj k À d. The circular chromatic number c ðGÞ of a graph G is the minimum of those k=d for which G admits a homomorphism to K k=d . The circular clique number ! c ðGÞ of G is the maximum of those k=d for which K k=d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have c ðHÞ ¼ ! c ðHÞ. In this paper, we prove that if G is circular perfect then for every vertex x of G, N G ½x is a perfect graph. Conversely, we prove that if for every vertex x of G, N G ½x is a perfect graph and G À N½x is a bipartite graph with no induced P 5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj os theorem for circular chromatic number for k=d ! 3. Namely, we shall design a few graph operations and prove that for any k=d ! 3, starting from the graph K k=d , one can construct all graphs of circular chromatic number at least k=d by repeatedly applying these graph operations.

📜 SIMILAR VOLUMES

Claw-free circular-perfect graphs

✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that

Convex-round graphs are circular-perfect

✍ Jørgen Bang-Jensen; Jing Huang 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB

## Abstract We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round grap

A generalization of perfect graphs?i-per

A generalization of perfect graphs?i-perfect graphs

✍ Cai, Leizhen; Corneil, Derek 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc

Cycle-perfect graphs are perfect

✍ Le, Van Bang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB 👁 2 views

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. 0 1996 John Wiley &

Circular permutation graphs

✍ D. Rotem; J. Urrutia 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 481 KB

β-Perfect Graphs

✍ S.E. Markossian; G.S. Gasparian; B.A. Reed 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 291 KB

The class of ;-perfect graphs is introduced. We draw a number of parallels between these graphs and perfect graphs. We also introduce some special classes of ;-perfect graphs. Finally, we show that the greedy algorithm can be used to colour a graph G with no even chordless cycles using at most 2(/(G