Grinstead's conjecture is true for graphs with a small clique number (Q2433715): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q226829 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Tadashi Sakuma / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2005.12.040 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028281168 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4242951 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topics on perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphical properties related to minimal imperfection / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3236733 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3490180 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The strong perfect graph theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220596 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On circular critical graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Grinstead's conjecture is true for graphs with a small clique number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Perfect zero–one matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2758338 / rank | |||
Normal rank |
Latest revision as of 22:25, 24 June 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