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 e ∉ S, and if s ∈ S, 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−1y ∈ S. 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.
Recommended Citation
Dizon-Garciano, A. V., Garces, I. J. L., & Ruiz, M. J. P. (2002). On Perfect Cayley Graphs. Electronic Notes in Discrete Mathematics, 11, 653-680.
