Grinstead's conjecture is true for graphs with a small clique number

DOI10.1016/J.DISC.2005.12.040MaRDI QIDQ2433715zbMATH OpenOpenAlexWikidataFDO

Authors Kenji Kashiwabara, Tadashi Sakuma

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.040

zbMATH Keywords

CGPW-graphcircular partitionable graphGrinstead's conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• A note on a cycle partition problem
• On the circular chromatic number of circular partitionable graphs
• On a cycle partition problem
• On classes of minimal circular-imperfect graphs
• On pseudo 2-factors
• Independent sets and chromatic numbers of circle graphs
• scientific article; zbMATH DE number 1286503
• Cycle partition of two-connected and two-edge connected graphs
• Every graph is an induced isopart of a circulant
• Circulant decompositions of certain multipartite graphs into Gregarious cycles of a given length

Cites work

• Graphical properties related to minimal imperfection
• Grinstead's conjecture is true for graphs with a small clique number
• scientific article; zbMATH DE number 3885919 (Why is no real title available?)
• scientific article; zbMATH DE number 3121699 (Why is no real title available?)
• scientific article; zbMATH DE number 4163144 (Why is no real title available?)
• scientific article; zbMATH DE number 1286503 (Why is no real title available?)
• On circular critical graphs
• Perfect zero–one matrices
• Some aspects of minimal imperfect graphs
• The strong perfect graph theorem
• Topics on perfect graphs

Cited in

(5)

• Grinstead's conjecture is true for graphs with a small clique number
• On circulant thin Lehman matrices
• On CIS circulants
• On circulant thin Lehman matrices
• Thin Lehman matrices arising from finite groups

This page was built for publication: Grinstead's conjecture is true for graphs with a small clique number

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