On classes of minimal circular-imperfect graphs

DOI10.1016/J.DAM.2007.05.045MaRDI QIDQ2482095zbMATH OpenOpenAlexFDO

Authors Arnaud Pêcher, Annegret K. Wagler

Publication date 16 April 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.045

zbMATH Keywords

circular coloring circular-perfection minimal circular-imperfect graph

Mathematics Subject Classification ID

Perfect graphs (05C17) Extremal problems in graph theory (05C35)

Review text

The authors prove the following results: {\parindent=5mm \begin{itemize} \item[1.]Let \(K_{p/q}\) be any prime circular clique. Then norm \((K_{p/q})\) is \begin{itemize} \item[(i)]circular-imperfect if and only if \(p\not\equiv-1\pmod q\) and \(\lfloor p/q\rfloor\geq 3\); \item[(ii)]minimal circular-imperfect if and only if \(p= 3q+ 1\) and \(q\geq 3\); \item[(iii)] isomorphic to \(\overline K_{p/3}\) if \(p= 3q+ 1\) and \(q\geq 3\). \end{itemize} \item[2.]All partitionable graphs apart from circular cliques are circular-imperfect. \item[3.]Outerplanar graphs are circular-perfect. \item[4.]The complete join \(G*G'\) of two graphs \(G\) and \(g'\) is \begin{itemize} \item[(i)]circular-perfect if and only if both \(G\) and \(G'\) are perfect; \item[(ii)]minimal circular-imperfect if and only if \(G\) is an odd hole or odd antihole and \(G'\) is a single vertex (or vice versa), that is if and only if \(G*G'\) is an odd wheel or an odd antiwheel. \end{itemize} \end{itemize}}

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On classes of minimal circular-imperfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482095)