Maximal-clique partitions and the roller coaster conjecture

DOI10.1016/J.JCTA.2016.06.019zbMATH Open1355.05184arXiv1412.4595OpenAlexW1456426994WikidataQ123186713 ScholiaQ123186713MaRDI QIDQ507795FDOQ507795

Authors: Jonathan Cutler, Luke Pebody 

Publication date: 9 February 2017

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

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.

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

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

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)

Cites Work

• Roots of independence polynomials of well covered graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bipartite graph with non-unimodal independent set sequence
• On the shape of a pure \(O\)-sequence
• Generalized covering designs and clique coverings
• Independence sequences of well-covered graphs: Non-unimodality and the roller-coaster conjecture
• Operations on well-covered graphs and the Roller-Coaster conjecture
• Clique coverings of graphs V: maximal-clique partitions

Cited In (5)

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

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)