Maximal-clique partitions and the roller coaster conjecture

DOI10.1016/J.JCTA.2016.06.019MaRDI QIDQ507795zbMATHOpenAlexWikidataFDO

Authors Jonathan Cutler, Luke Pebody

Publication date 9 February 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4595

zbMATH Keywords

independence polynomialwell-covered graphsclique coverings

Mathematics Subject Classification ID

Graph polynomials (05C31) 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)

Abstract: A graph $G$ is {em well-covered} if every maximal independent set has the same cardinality $q$. Let $i_k(G)$ denote the number of independent sets of cardinality $k$ in $G$. Brown, Dilcher, and Nowakowski conjectured that the independence sequence $(i_0(G),i_1(G),ldots,i_q(G))$ was unimodal for any well-ordered graph $G$ with independence number $q$. Michael and Traves disproved this conjecture. Instead they posited the so-called ``Roller Coaster" Conjecture: that the terms [ i_{leftlceilfrac{q}2 ight ceil}(G), i_{leftlceilfrac{q}2 ight ceil+1}(G), ldots, i_q(G) ] could be in any specified order for some well-covered graph $G$ with independence number $q$. Michael and Traves proved the conjecture for $q<8$ and Matchett extended this to $q<12$. In this paper, we prove the Roller Coaster Conjecture using a construction of graphs with a property related to that of having a maximal-clique partition. In particular, we show, for all pairs of integers $1lek<q$ and positive integers $m$, that there is a well-covered graph $G$ with independence number $q$ for which every independent set of size $k+1$ is contained in a unique maximal independent set, but each independent set of size $k$ is contained in at least $m$ distinct independent sets.

Recommendations

• Independence sequences of well-covered graphs: Non-unimodality and the roller-coaster conjecture
• scientific article; zbMATH DE number 1990727
• Operations on well-covered graphs and the Roller-Coaster conjecture
• The roller-coaster conjecture revisited
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture

Cites work

• scientific article; zbMATH DE number 5139526 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• A bipartite graph with non-unimodal independent set sequence
• Clique coverings of graphs V: maximal-clique partitions
• Generalized covering designs and clique coverings
• Independence sequences of well-covered graphs: Non-unimodality and the roller-coaster conjecture
• On the shape of a pure \(O\)-sequence
• Operations on well-covered graphs and the Roller-Coaster conjecture
• Roots of independence polynomials of well covered graphs

Cited in

(5)

• The roller-coaster conjecture revisited
• Almost unimodal and real-rooted graph polynomials
• Independence polynomials of bipartite graphs
• Independent set and matching permutations
• Operations on well-covered graphs and the Roller-Coaster conjecture

This page was built for publication: Maximal-clique partitions and the roller coaster conjecture

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