polynomial-time algorithmstrong cliquediamond-free graphNP-hard problemCIS graphmaximal cliquemaximal stable setstrongly perfect graphsimplicial cliqueErdős-Hajnal property
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Abstract: A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved ErdH{o}s-Hajnal property for such graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3878985 (Why is no real title available?)
- scientific article; zbMATH DE number 3926973 (Why is no real title available?)
- scientific article; zbMATH DE number 4093496 (Why is no real title available?)
- scientific article; zbMATH DE number 1076150 (Why is no real title available?)
- scientific article; zbMATH DE number 861332 (Why is no real title available?)
- scientific article; zbMATH DE number 970798 (Why is no real title available?)
- A New Algorithm for Generating All the Maximal Independent Sets
- A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A characterization and hereditary properties for partition graphs
- A characterization of claw-free CIS graphs and new results on the order of CIS graphs
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A decomposition for strongly perfect graphs
- Algorithmic graph theory and perfect graphs
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- An algorithm for finding clique cut-sets
- An algorithm to recognize a middle graph
- Bipartite bihypergraphs: a survey and new results
- Classes of perfect graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Coloring edges and vertices of graphs without short or long cycles
- Coloring perfect \((K_ 4\)-e)-free graphs
- Colouring diamond-free graphs
- Complexity results for well‐covered graphs
- Convex Bodies, Graphs and Partial Orders
- Decomposition by clique separators
- Detecting strong cliques
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Equistable graphs
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Finding large holes
- Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
- Graph-Theoretic Concepts in Computer Science
- Graph-based data clustering with overlaps
- Graphs vertex-partitionable into strong cliques
- Not complementary connected and not CIS d-graphs form weakly monotone families
- Obstructions for three-coloring graphs without induced paths on six vertices
- On CIS circulants
- On a conjecture of Meyniel
- On equistable, split, CIS, and related classes of graphs
- On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
- On graphs whose maximal cliques and stable sets intersect
- On graphs with polynomially solvable maximum-weight clique problem
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
- Ramsey-type theorems
- Strong cliques and equistability of EPT graphs
- Strong cliques in diamond-free graphs
- The Erdős-Hajnal conjecture. A survey
- Topics on perfect graphs
- Vertex-transitive CIS graphs
Cited in
(11)- Strong cliques and equistability of EPT graphs
- On graphs without a \(C_{4}\) or a diamond
- Detecting strong cliques
- scientific article; zbMATH DE number 6432456 (Why is no real title available?)
- In memory of Jérôme Monnot
- Strong cliques in vertex‐transitive graphs
- On weakly diamond-free Berge graphs
- Recognition algorithm for diamond-free graphs
- Finding a strong stable set or a Meyniel obstruction in any graph
- Linear χ -binding functions for some classes of ( P 3 ∪ P 2 )-free graphs
- Total domination, separated-cluster, CD-coloring: algorithms and hardness
This page was built for publication: Strong cliques in diamond-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919069)
