Equistarable graphs and counterexamples to three conjectures on equistable graphs

DOI10.1002/JGT.22040zbMATH Open1359.05054arXiv1407.1670OpenAlexW1778521510WikidataQ122906500 ScholiaQ122906500MaRDI QIDQ2978190FDOQ2978190

Authors: Martin Milanič, Nicolas Trotignon 

Publication date: 21 April 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight $1$. In $1994$, Mahadev et al.~introduced a subclass of equistable graphs, called strongly equistable graphs, as graphs such that for every $cle1$ and every non-empty subset $T$ of vertices that is not a maximal stable set, there exist positive vertex weights such that every maximal stable set is of total weight $1$ and the total weight of $T$ does not equal $c$. Mahadev et al. conjectured that every equistable graph is strongly equistable. General partition graphs are the intersection graphs of set systems over a finite ground set $U$ such that every maximal stable set of the graph corresponds to a partition of $U$. In $2009$, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An intermediate conjecture, one that would follow from Orlin's conjecture and would imply the conjecture by Mahadev, Peled, and Sun, was posed by Miklaviv{c} and Milaniv{c} in $2011$, and states that every equistable graph has a clique intersecting all maximal stable sets. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle-free graphs.

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

Recommendations

• Equistarable bipartite graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Equistable simplicial, very well-covered, and line graphs
• Equistable graphs
• Complexity results for equistable graphs and related classes

zbMATH Keywords

line graphequistable graphgeneral partition graphconjecturegraph complementstrongly equistable graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Equistable series-parallel graphs
• Equistable chordal graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• A characterization and hereditary properties for partition graphs
• Recent examples in the theory of partition graphs
• Equistable simplicial, very well-covered, and line graphs
• Equistable distance-hereditary graphs
• On equistable, split, CIS, and related classes of graphs
• Title not available (Why is that?)
• On partition graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equistable graphs
• Title not available (Why is that?)
• Complexity results for equistable graphs and related classes
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• On n-extendable graphs
• Structural results for general partition, equistable and triangle graphs
• Extending matchings in graphs: A survey

Cited In (17)

• Short proofs on the structure of general partition, equistable and triangle graphs
• Counterexamples to three conjectures concerning perfect graphs
• Strong cliques and equistability of EPT graphs
• Equistarable bipartite graphs
• Complexity results for equistable graphs and related classes
• Detecting strong cliques
• Strong cliques in diamond-free graphs
• Equistable chordal graphs
• Recognizing \(k\)-equistable graphs in FPT time
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Structural results for general partition, equistable and triangle graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Equistable simplicial, very well-covered, and line graphs
• Equistable distance-hereditary graphs
• Decomposing 1-Sperner hypergraphs
• Graphs vertex-partitionable into strong cliques
• On three extensions of equimatchable graphs

This page was built for publication: Equistarable graphs and counterexamples to three conjectures on equistable graphs

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