Equistarable graphs and counterexamples to three conjectures on equistable graphs

DOI10.1002/JGT.22040MaRDI QIDQ2978190zbMATH OpenOpenAlexWikidataFDO

Authors Martin Milanič, Nicolas Trotignon

Publication date 21 April 2017

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

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

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)

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.

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

Cites work

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

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
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Recognizing k-equistable graphs in FPT time
• 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)