Is there a better term for "complete k-partite graph" in the case where k is not fixed? If I say "complete k-partite graph", people tend to assume "for some particular k".

In other words, what's a term for any graph for whom each connected component in the complement graph is a clique?

I asked this before, but it was as part of another question, so it was ignored.


3 Answers 3


How about this: Call your graphs simply $(K_1 + K_2)$-free graphs, where $K_n$ is the complete graph with $n$ vertices, + stands for disjoint union, and $H$-free means without $H$ as an induced subgraph.

  • 1
    $\begingroup$ I don't think that means the same thing. For instance, the four-vertex graph which is simply 3 edges joined in a line is not a complete k-partite graph, but it is (K_1+K_2)-free $\endgroup$
    – dspyz
    Commented Feb 18, 2014 at 2:56
  • $\begingroup$ I edited my question to clarify. By "is a set of disjoint cliques" I meant "each connected component is a clique" $\endgroup$
    – dspyz
    Commented Feb 18, 2014 at 3:00
  • 6
    $\begingroup$ @dspyz your 4-vertex example is NOT (K1+K2)-free. Note: complete multipartite graphs and (K1+K2)-free graphs coincide. $\endgroup$ Commented Feb 18, 2014 at 14:00
  • $\begingroup$ Ok, I see that every complete multipartite graph is (K1+K2) free and also that my example was wrong, but it's still not obvious to me that the converse is true. Do you have a proof? $\endgroup$
    – dspyz
    Commented Feb 18, 2014 at 22:15
  • $\begingroup$ @dspyz your observation is a proof: complete multipartite = each connected component is a clique = co-(K1+K2)-free = P3-free = cluster graphs (cf. Bangye's answer). $\endgroup$ Commented Feb 19, 2014 at 11:06

I believe the most standard term is complete multipartite graph.

  • $\begingroup$ Yes, I think you see this often. This generalizes the complete bipartite graph $K_{s,t}$ used by some authors. $\endgroup$
    – Juho
    Commented Feb 18, 2014 at 12:23
  • $\begingroup$ Moreover, I have seen the notation $K_{a_1,a_2,\dots,a_k}$ used, for a complete multipartite graph with partitions of sizes $a_1, a_2,\dots, a_k$. $\endgroup$ Commented Feb 18, 2014 at 13:06
  • 4
    $\begingroup$ The notation applies only for fixed k. $\endgroup$ Commented Feb 18, 2014 at 15:42
  • 1
    $\begingroup$ @TobiasMüller: Are you commenting on the answer or on the previous comment? $\endgroup$ Commented Feb 19, 2014 at 0:05
  • $\begingroup$ @SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$. $\endgroup$ Commented Feb 19, 2014 at 10:57

A cluster graph consists of disjoint maximal cliques, i.e., each connected component is a clique. Your complete k-partite graph for non-fixed k is the complement of a cluster graph. Also, a graph is cluster graph iff it is "induced $P_3$-free". Modifying a graph into a cluster graph with minimum number of edge insertions and deletions has been extensively studied in the area of parameterized algorithms. You can google "cluster graph editing" or "correlation clustering" to find them.

  • $\begingroup$ Sorry, what's P_3? $\endgroup$
    – dspyz
    Commented Feb 20, 2014 at 16:49
  • 1
    $\begingroup$ $P_3$ is a path of three nodes. Three nodes with exactly two edge is an induced $P_3$. These are common notation in graph theory. $\endgroup$
    – Bangye
    Commented Feb 21, 2014 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.