For p>=2q¡Alet Kp/q be the graph with vertices 0¡A1¡A2¡A¡K¡Ap-1 in which
i~j if q<=|i-j|<=p-q. The circular chromatic number Xc(G) of a graph G is the
minimum of those p/q for which G admits a homomorphism to Kp/q. The circular clique number Wc(G) of G is the maximum of those p/q for which Kp/q admits a homomorphism to G.. A graph G is circular perfect if for every induced subgraph
H of G we have Xc(H)=Wc(H). In this paper,we characterize those rational
numbers p/q for which the complement of Kp/q are circular perfect. We also prove
that if G(n¡AS) is a circulant graph whose generating set S has cardinality at most
3¡Athen G(n¡AS) is circular perfect.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0618105-000001 |
| Date | 18 June 2005 |
| Creators | Yang, Chao-Chi |
| Contributors | Xuding Zhu, D. J. Guan, Li-Da Tong, Tsai-Lien Wong |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0618105-000001 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0017 seconds