Grinstead's conjecture is true for graphs with a small clique number (Q2433715): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q122908143, #quickstatements; #temporary_batch_1706974288397 |
Removed claim: author (P16): Item:Q226829 |
||
Property / author | |||
Property / author: Tadashi Sakuma / rank | |||
Revision as of 13:54, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Grinstead's conjecture is true for graphs with a small clique number |
scientific article |
Statements
Grinstead's conjecture is true for graphs with a small clique number (English)
0 references
30 October 2006
0 references
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.
0 references
circular partitionable graph
0 references
CGPW-graph
0 references
Grinstead's conjecture
0 references