A note on simplicial cliques Chudnovsky, Maria; Scott, Alex; Seymour, Paul ...
Discrete mathematics,
September 2021, 2021-09-00, Volume:
344, Issue:
9
Journal Article
Peer reviewed
Open access
Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such ...that for every vertex v∈K, the set of neighbours of v outside of K is a clique. In fact, we prove the existence of a simplicial clique in a more general class of graphs defined by forbidden induced subgraphs.
Strong cliques in diamond-free graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Theoretical computer science,
02/2021, Volume:
858
Journal Article
Peer reviewed
Open access
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 all remain NP-hard or co-NP-hard 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 three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
•A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets.•We study strong cliques in the class of diamond-free graphs.•We characterize diamond-free CIS graphs and study their Erdős-Hajnal property.•We characterize co-strongly perfect diamond-free graphs.•We derive hardness results for five related problems.
Growing Without Cloning Chudnovsky, Maria; Seymour, Paul
SIAM journal on discrete mathematics,
01/2012, Volume:
26, Issue:
2
Journal Article
Peer reviewed
A graph $G$ is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph $K_{1,3}$, and it is prime if $|V(G)| \geq 4$ and there is no $X \subseteq V(G)$ with ...$1<|X|<|V(G)|$ such that every vertex of $V(G) \setminus X$ with a neighbor in $X$ is adjacent to every vertex of $X$. In particular, if $G$ is prime, then both $G$ and $G^c$ are connected. This paper has two main results. The first one is that if $G$ is a prime graph that is not a member of a particular family of exceptions, and $H$ is a prime induced subgraph of $G$, then (up to isomorphism) $G$ can be grown from $H$, adding one vertex at a time, in such a way that all the graphs constructed along the way are prime induced subgraphs of $G$. A simplicial clique in $G$ is a nonempty clique $K$ such that for every $k \in K$ the set of neighbors of $k$ in $V(G) \setminus K$ is a clique. Our second result is that a prime claw-free graph $G$ has at most $|V(G)|+1$ simplicial cliques, and we give an algorithm to find them all with running time $O(|V(G)|^4)$. In particular, this answers a question of Prasad Tetali private communication who asked if there is an efficient algorithm to test if a claw-free graph has a simplicial clique. Finally, we apply our results to claw-free graphs that are not prime. Such a graph may have exponentially many simplicial cliques, so we cannot list them all in polynomial time, but we can in a sense describe them. PUBLICATION ABSTRACT
PDF
