Terminology for complete k-partite graph where k is not fixed

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.

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.

• 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 Commented Feb 18, 2014 at 2:56
• I edited my question to clarify. By "is a set of disjoint cliques" I meant "each connected component is a clique" Commented Feb 18, 2014 at 3:00
• @dspyz your 4-vertex example is NOT (K1+K2)-free. Note: complete multipartite graphs and (K1+K2)-free graphs coincide. Commented Feb 18, 2014 at 14:00
• 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? Commented Feb 18, 2014 at 22:15
• @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). Commented Feb 19, 2014 at 11:06

I believe the most standard term is complete multipartite graph.

• Yes, I think you see this often. This generalizes the complete bipartite graph $K_{s,t}$ used by some authors.
– Juho
Commented Feb 18, 2014 at 12:23
• 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$. Commented Feb 18, 2014 at 13:06
• The notation applies only for fixed k. Commented Feb 18, 2014 at 15:42
• @TobiasMüller: Are you commenting on the answer or on the previous comment? Commented Feb 19, 2014 at 0:05
• @SergeGaspers My comment is about the notation $K_{s,t}$, $K_{a_1,a_2,\ldots,a_k}$. 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.

• Sorry, what's P_3? Commented Feb 20, 2014 at 16:49
• $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. Commented Feb 21, 2014 at 0:21