On Perfect Cayley Graphs
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 cho...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Published: |
Archīum Ateneo
2002
|
| Subjects: | |
| Online Access: | https://archium.ateneo.edu/mathematics-faculty-pubs/84 https://www.sciencedirect.com/science/article/abs/pii/S157106530400112X?via%3Dihub#! |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Ateneo De Manila University |
| Summary: | 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. |
|---|