Abstract: Recently, Milaniv{c} and Trotignon introduced the class of equistarable graphs as graphs without isolated vertices admitting positive weights on the edges such that a subset of edges is of total weight if and only if it forms a maximal star. Based on equistarable graphs, counterexamples to three conjectures on equistable graphs were constructed, in particular to Orlin's conjecture, which states that every equistable graph is a general partition graph. In this paper we characterize equistarable bipartite graphs. We show that a bipartite graph is equistarable if and only if every -matching of the graph extends to a matching covering all vertices of degree at least . As a consequence of this result, we obtain that Orlin's conjecture holds within the class of complements of line graphs of bipartite graphs. We also connect equistarable graphs to the triangle condition, a combinatorial condition known to be necessary (but in general not sufficient) for equistability. We show that the triangle condition implies general partitionability for complements of line graphs of forests, and construct an infinite family of triangle non-equistable graphs within the class of complements of line graphs of bipartite graphs.
Recommendations
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
- Equistable simplicial, very well-covered, and line graphs
- Short proofs on the structure of general partition, equistable and triangle graphs
- Structural results for general partition, equistable and triangle graphs
Cites work
- scientific article; zbMATH DE number 4066957 (Why is no real title available?)
- A characterization and hereditary properties for partition graphs
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A structure theorem for maximum internal matchings in graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Deciding the deterministic property for soliton graphs
- Equistable chordal graphs
- Equistable distance-hereditary graphs
- Equistable graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
- Equistable simplicial, very well-covered, and line graphs
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- Matching theory
- Maximum matching and a polyhedron with 0,1-vertices
- On n-extendable graphs
- Oriented star packings
- Recent examples in the theory of partition graphs
- Tutte type theorems for graphs having a perfect internal matching
Cited in
(11)- Bipolarizable graphs
- scientific article; zbMATH DE number 844141 (Why is no real title available?)
- Short proofs on the structure of general partition, equistable and triangle graphs
- Equistable simplicial, very well-covered, and line graphs
- Graphs vertex-partitionable into strong cliques
- Detecting strong cliques
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- 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
- Strong cliques and equistability of EPT graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
This page was built for publication: Equistarable bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q279223)
