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?
Hi Nazanin! I think the answer is 0, in general. If I understood it well, for k=3 and sets of size 2, you have this counterexample.
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 Nazanin, you have k sets of vertices and are looking for Kk graphs.
Is it the same k (number of sets = number of vertices in the complete graph)?
"X-colorable" is unclear to me as well.
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 Nazanin, thank you for the interesting and fun question!
Without any complementary assumptions, it seems to me that:
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}.
I am pretty sure that:
If there is no singleton, one can avoid k-cycles. Absence of k-cycle makes the existence of Kk impossible.
For the situation you mentioned, see the figure.
Dear Viera, this graph is 2-chromatic as it does not contain any odd cycle. But, in my condition the graph should be 3-chromatic.
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.
Take a graph C5 and an extra 2-path between two adjacent vertices. Then the maximum size of the color classes is 2 but the number of triangles is one.
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.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs