Equistable simplicial, very well-covered, and line graphs

DOI10.1016/j.dam.2013.01.022zbMath1288.05215OpenAlexW2065354512MaRDI QIDQ2448905

Martin Milanič, Vadim E. Levit

Publication date: 5 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.01.022

zbMATH Keywords

polynomial time algorithmline graphsimplicial graphtriangle conditionequistable graphgeneral partition graphtriangle graphvery well-covered graphstrongly equistable graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (9)

Equistarable bipartite graphs ⋮ Structural results for general partition, equistable and triangle graphs ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs ⋮ Short proofs on the structure of general partition, equistable and triangle graphs ⋮ Recognizing k-equistable Graphs in FPT Time ⋮ Detecting strong cliques ⋮ Decomposing 1-Sperner hypergraphs ⋮ Strong cliques and equistability of EPT graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity results for equistable graphs and related classes
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Trivially perfect graphs
• Equistable series-parallel graphs
• Equistable chordal graphs
• Very well covered graphs
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Quasi-threshold graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• On the complexity of the independent set problem in triangle graphs
• 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 distance-hereditary graphs
• Independent Domination in Triangle Graphs
• Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
• Efficiency of a Good But Not Linear Set Union Algorithm
• Randomly matchable graphs
• Graph Classes: A Survey
• Equistable graphs
• Faster scaling algorithms for general graph matching problems
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Some covering concepts in graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Equistable simplicial, very well-covered, and line graphs