Grinstead's conjecture is true for graphs with a small clique number (Q2433715): Difference between revisions

A graph \(G\) is called partitionable if there exist integers \(p\) and \(q\) such that for every \(v\in V(G)\), the graph \(G-v\) can be partitioned into \(p\) cliques of size \(q\) and into \(q\) independent sets of size \(p\). Call a graph \(G\) circular if it is isomorphic to a graph \(H\) with \(V(H)= \mathbb{Z}_n\) (the cyclic group of order \(n\)) and where \(Q\) is a maximum clique of \(H\) if and only if \(Q+ 1:= \{q+ 1\in\mathbb{Z}_n: q\in Q\}\) is a maximum clique of \(H\). A special class of circular partitionable graphs had been constructed by \textit{V. Chvátal}, \textit{R. L. Graham}, \textit{A. F. Perold} and \textit{S. H. Whitesides} in [Perfect graphs, Ann. Discrete Math. 21, 197--206 (1984; Zbl 0556.05012)]. These graphs are thus called CGPW-graphs. Grinstead's conjecture claims that every circular partitionable graph is a CGPW-graph. In this context it is natural to classify circular partitionable graphs \(G\) by their clique number \(\omega(G)\) and their independence number \(\alpha(G)\). Set \(m=\min(\omega(G), \alpha(G))\). The authors prove that Grinstead's conjecture is true if \(m\leq 8\), thus improving an earlier result by Bacsó et al. who had shown the validity of Grinstead's conjecture for the cases \(m\leq 5\). In fact, the authors need to consider the three cases \(m\in\{6,7,8\}\) separately. They also note that they have succeeded in proving Grinstead's conjecture if \(m\leq 15\), this latter result is being published in a separate paper.