Equistable simplicial, very well-covered, and line graphs
We verify the conjectures of MahadevPeledSun and of Orlin, both related to equistable graphs, for the classes of simplicial, very well-covered and line graphs. Our results are based on the combinatorial features of triangle graphs and general partition graphs. In particular, we obtain several equivalent characterizations of equistable simplicial graphs, equistable very well-covered graphs, and equistable line graphs, some of which imply polynomial time recognition algorithms for graphs in these classes.
line graph equistable graph triangle graph general partition graph simplicial graph very well-covered graph strongly equistable graph triangle condition polynomial time algorithm