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 |
id |
ph-ateneo-arc.mathematics-faculty-pubs-1083 |
---|---|
record_format |
eprints |
spelling |
ph-ateneo-arc.mathematics-faculty-pubs-10832020-06-16T06:31:04Z On Perfect Cayley Graphs Garciano, Agnes Garces, Ian June L Ruiz, Mari-Jo P 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. 2002-01-01T08:00:00Z text https://archium.ateneo.edu/mathematics-faculty-pubs/84 https://www.sciencedirect.com/science/article/abs/pii/S157106530400112X?via%3Dihub#! Mathematics Faculty Publications Archīum Ateneo Perfect graph Cayley graph graph factorization Geometry and Topology Mathematics |
institution |
Ateneo De Manila University |
building |
Ateneo De Manila University Library |
country |
Philippines |
collection |
archium.Ateneo Institutional Repository |
topic |
Perfect graph Cayley graph graph factorization Geometry and Topology Mathematics |
spellingShingle |
Perfect graph Cayley graph graph factorization Geometry and Topology Mathematics Garciano, Agnes Garces, Ian June L Ruiz, Mari-Jo P On Perfect Cayley Graphs |
description |
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. |
format |
text |
author |
Garciano, Agnes Garces, Ian June L Ruiz, Mari-Jo P |
author_facet |
Garciano, Agnes Garces, Ian June L Ruiz, Mari-Jo P |
author_sort |
Garciano, Agnes |
title |
On Perfect Cayley Graphs |
title_short |
On Perfect Cayley Graphs |
title_full |
On Perfect Cayley Graphs |
title_fullStr |
On Perfect Cayley Graphs |
title_full_unstemmed |
On Perfect Cayley Graphs |
title_sort |
on perfect cayley graphs |
publisher |
Archīum Ateneo |
publishDate |
2002 |
url |
https://archium.ateneo.edu/mathematics-faculty-pubs/84 https://www.sciencedirect.com/science/article/abs/pii/S157106530400112X?via%3Dihub#! |
_version_ |
1681506677574074368 |