Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with clique
Search options answers only
not deleted
user 472
A clique is a subset of the vertices of a graph such that every pair of vertices in the subset is connected by an edge.
3
votes
Accepted
Implementing Nesetril and Poljak's clique detection algorithm
The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication. …
- 22.8k
4
votes
Accepted
Can I find a clique with more than 2 nodes in a bipartite graph?
A clique of size at least 3 contains a triangle, and a triangle $K_3$ clearly cannot be colored with 2 colors. …
- 22.8k
2
votes
Accepted
Applications of the splittance of a graph/ Turning graphs into splitgraphs
There is nothing deeper to it than what you describe: if the graph is split or it has "small" distance to being split (e.g., you can make it split by removing a small number of edges/vertices), you mi …
- 22.8k
2
votes
Accepted
Understanding CLIQUE structure
So assume $G$ contains a clique of size $k$, and you have a proper coloring with less than $k$ colors. It follows that the clique contains at least two vertices with the same color. … Further, one might also wonder if the chromatic number of a graph would always equal the clique number. …
- 22.8k
3
votes
Accepted
Algorithm to compute partitions of a graph in N cliques
This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known. …
- 22.8k
5
votes
Accepted
The equivalence relations cover problem (in graph theory)
It is upper bounded by the clique covering number (the minimum collection of cliques such that each edge of the graph is in at least one clique). …
- 22.8k
3
votes
Maximal cliques in a multipartite graph - efficient?
A maximal clique and a maximum clique are in general different. … A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. …
- 22.8k
2
votes
Clique-problem for planar graph
So suppose the problem is "is there a clique of size $k$ in a given planar graph $G$?" Now, if $k \geq 5$, we immediately answer NO. … If any one of them induces a $k$-clique, we answer YES. Otherwise, we answer NO. Hence, the problem is in P. …
- 22.8k