×

Circular perfect graphs. (English) Zbl 1183.05051

Balakrishnan, R. (ed.) et al., Proceedings of the international conference on discrete mathematics (ICDM 2006), Bangalore, India, December 15–18, 2006. Mysore: Ramanujan Mathematical Society (ISBN 978-81-902545-7-1/hbk). Ramanujan Mathematical Society Lecture Notes Series 7, 131-140 (2008).
Summary: For \(1\leq d\leq k\), let \(K_{k/d}\) be the graph with vertices \(0,1,\dots,k-1\), in which \(i\sim j\) if \(d\leq|i-j|\leq k-d\). The circular chromatic number \(\chi_c(G)\) of a graph \(G\) is the minimum of those \(k/d\) for which \(G\) admits a homomorphism to \(K_{k/d}\). The circular clique number \(\omega_c(G)\) of \(G\) is the maximum of those \(k/d\) for which \(K_{k/d}\) admits a homomorphism to \(G\). A graph \(G\) is circular perfect if for every induced subgraph \(H\) of \(G\) we have \(\chi_c(H) =\omega_c(H)\). This paper surveys results on circular perfect graphs.
For the entire collection see [Zbl 1152.05003].

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite