Title

On Perfect Cayley Graphs

Document Type

Article

Publication Date

2002

Abstract

A graph is perfect if each of its induced subgraphs H has the property that its chromatic number χ(H) equals its clique number ω(H). The Strong Perfect Graph Conjecture (SPGC) states: An undirected graph is perfect if and only if neither G nor its complement G contains, as an induced subgraph, a chordless cycle whose length is odd and at least 5. In this paper we show that SPGC holds for minimal Cayley graphs. Let G be a finite group and S a generating set for G with eS, and if sS, then s−1 ∈ S. The Cayley graph determined by the pair (G, S), and denoted by Γ(G, S), is the graph with vertex set V(Γ) consisting of the following elements: (x, y) ∈ E(Γ) if and only if x−1yS. A Cayley graph is minimal if no proper subset of its generating set also generates G.

We also give a sufficient condition for Cayley graphs derived from permutation groups to be perfect, prove that certain P2, C3 factorizations yield perfect general graphs, and identify families of perfect Cayley graphs.

Share

COinS