If there are k sets of vertices in a graph, with the condition that each vertex in a set should be connected to at least one vertex from each of the other sets, then what is the least number of complete sub-graphs $K_{k}$ in this graph?
In fact, if there is no edge inside the sets, but you can guarantee a minimum density of the graph, then I think Turan's theorem may be useful to find K_k subgraphs.
Hi dear Dr. Antoni ! Thank you for your answer and the figure. Yes, that's true. But, is it working when the number of vertices in each of the sets are different? And also when the graph is k-chromatiic?
Here you have another counterexample, is this what you mean?
I don't understand your question about being $\chi$-colorable. Usually, $\chi(G)$ stands for the chromatic number of G... In the case of the graph I sent, it's 2-colorable.
Dear Dr. Antoni and Dr. Viera, thank you for your answers. I mean the chromatic number of the graph is k. Means $\chi(G)=k$ and each of the sets has different colors. The vertices those are inside a set have the same colors and the graph is k-chromatic graph. So, we have k color classes. Dear Dr. Viera, yes it is the same k as in Kk.
Dear Dr. Peter, in the example of Dr. Antoni it is not equal to 1. But, I am looking for an answer in the graphs in which the number of vertices in the color classes are not all equal.
Dear Viera, thank you for your answer. I think it does not work for a 3-chromatic graph in which the number of vertices in the color classes are from the set {2,2,3}.
Dear Viera, in the 7th message I have explained that X(G) = k. . So in this graph X(G) should be 3 but it is not. In the 10th message I have also mentioned that the graph is 3-chromatic. It means X(G) = 3.
Dear Dr. Radhakrishnan, here is the complete version of my question:
What is the least number of complete subgraphs Kk in a k-chromatic graph G in which each vertex in a color class is connected to all the other color classes with at least one edge, with the condition that the number of vertices of the color classes are not all equal?
Dear Peter, take 2 triangles those have only one vertex in common. Then the maximum size of color classes is 3 but the number of complete graphs K3 , is 2.
Dear Peter, I am sorry that I did not get your point. {A1 B2} and {A2 B1} are also disconnected. And when there is no edge between them, it will not be a subgraph of G. It is in the complement of G. Please send me your answer more clear, if possible.
As for the example from the previous page, I concour with Peter.
The maximal size of colour classes in the given example is 2 (the sizes are 1,2,2). There are 2 complete subgraphs K3.
However, I think that the result is 2 thanks to one singleton in the assembly.
If returning to the case with 2,2,3 vertices in the respective classes, we are sure to obtain one K3, and it is possible to have no other triangle there.
Dear Peter, C5 is a cycle of length 5 and 2-path is a path of length 2. Adding a 2-path between two adjacent vertices means we add an extra vertex and then connect the vertex to two adjacent vertices by two extra edges. Here are the figures.