{'fraction_non_alphanumeric': 0.05054371465854719, 'fraction_numerical': 0.01574597651152675, 'mean_word_length': 3.5153181461115475, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the number of star-shaped classes in optimal colorings of Kneser graphs

A family of sets is called star-shaped if all the members of the family have a point in common. The main aim of this paper is to provide a negative answer to the following question raised by James Aisenberg et al [Short proofs of the kneser-Lovasz coloring principle, Information and Computation, 261:296-310, 2018.], for the case k=2.


Introduction
In this paper all graphs are finite, undirected and simple. A (proper) coloring of a graph is an assignment of colors to its vertices such that no two adjacent vertices have the same color. The chromatic number χ(H) of a graph H is the smallest number of colors in a coloring of H. For a given coloring of a graph H, a subgraph of H is called colorful if all its vertices receives different colors. The (n, k)-Kneser graph KG(n, k) is a graph whose vertices correspond to all k-subsets of the set [n] = {1, 2 . . . , n}, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Finally, a family F of sets is called star-shaped if F = ∅. Almost seventy years ago, a purely combinatorial conjecture was raised by Kneser which in the language of graph theory is equivalent to say χ(KG(n, k)) = n − 2k + 2 for n 2k − 1. About two decades later, Lovász [12] proved Kneser's conjecture by taking an extraordinary approach, using tools from algebraic topology. Since then, many attentions have been drawn to study various problems related to this conjecture, including a large number of new proofs such as [4,9,11,13], and many generalizations such as [2,3,10,14,5,8,6]. In particular, James Aisenberg et al [1] gave a new proof of this conjecture uses a simple counting argument based on the Hilton-Milner theorem, for all but finitely many cases 1 .
Indeed, their main idea was based on that fact that if there was an (n − 2k + 1)-coloring of KG(n, k), then it would contain a star-shaped color class [1, Lemma 8] provided that n is enough large 2 . Then removing this vertex would lead to a ((n − 1) − 2k + 1)-coloring of KG(n − 1, k). So, to verify the conjecture one just needs to check the validity of the conjecture for finitely many base cases which can be checked, for instance, using the topological arguments provided by Lovász for these cases 3 .
Actually, they showed if there was such a coloring then it would contain many star-shaped color classes [1, Lemma 9], again provided n is enough large. Motivated by this result, they showed that there is an optimal coloring ( a coloring with (n − 2k + 2) colors) of KG(n, k) with (k − 1) star-shaped color classes provided that n 3k − 3 and then they raised the following question in this regard.
The main objective of this paper is to give a negative answer to the above question for the case k = 2. As a corollary, this result leads to a purely combinatorial proof for the K l,m -Theorem [15,Theorem 2] for the case KG(n, 2). More precisely, for every non-negative integers k, l with k + l + m = n − 2, and any optimal proper coloring of KG(n, 2), there is a colorful complete bipartite K l,m subgraph in KG(n, 2). A similar result for existence of colorful complete tripartite sungraph in KG(n, 2) will be provided as as well.

Main Results
First note that we can view KG(n, 2) as the complement of the line graph of the complete graph K n and therefore proper colorings of KG(n, 2) are exactly partitions of the edge set of the complete graphs K n into stars and triangles. More generally, as mentioned here [7], if G is the complement of the line graph of a graph H, then proper colorings of G are exactly partitions of the edge set of H into stars and triangles. A star is a tree with a vertex, the center of the star, connected to all other vertices. A single-edge tree is in particular a star. In this particular case, we will always assume that exactly one of the two vertices has been identified as the center, so as to be in a position of always speak of the center of a star without ambiguity. A triangle is a circuit of length 3. We call such a partition of H into stars and triangles an ST-partition. Lemma 1. Consider an optimal ST-partition P of a graph H. Then, at most one vertex of each triangle in P can be the center of a star. Proof. We proceed by a contradiction. Suppose that T is a triangle in P with at least two vertices x, y such that each of them is also the center of a star, name it S x , and S y respectively. Then we can add the two edges of T incident to x to S x , and the remaining edge of T to S y , and finally remove T from S. This leads to a new ST-partition with fewer elements which contradicts the optimality of P.

Lemma 2.
Consider an optimal ST-partition P of a graph H. If there is a triangle T in P, then each vertex x of H which does not belong to any triangle of P and it is connected to at least two vertices of T is the center of a star.
Proof. We will use a proof by contradiction. Suppose x is not the center of any star. If a, b are two vertices of T which are connected to x, then each of the edges {a, x} and {b, x} must belong to a star or a triangle in P. These imply that a and b are both must be the center of stars, as no triangle in P having x as its vertices, which contradicts the previous lemma.

Theorem 1.
There is no optimal ST-partition of the complete graph K n with more than one triangle. Moreover, if n 3, any optimal ST-partition of K n contains exactly one triangle.
Proof. Suppose the contrary and choose the minimum integer n with the property that there is an optimal ST-partition P of the complete graph K n with more than one triangle. Let T 1 , . . . , T k be the list of all the triangles in P where k 2. Let A = k i=1 V (T i ) be the set of the vertices of these triangles, B ⊆ [n] \ A be the set of the rest vertices which are centers of stars, and finally put C = [n] \ (A ∪ B). By Lemma 2, we have C = ∅. Moreover, Lemma 1 implies B = ∅. Indeed, if there was a vertex of K n in B, then removing this vertex leads to an optimal ST-partition with at least two triangles for K n−1 , which would contradict the minimality of n, and therefore we must have B = ∅. In summery, we have shown that any vertex of K n belongs to at least one of these triangles T 1 , . . . , T k . Now, we consider two cases: Case I. First, we consider the case that there are exactly two triangles in P, say T 1 , and T 2 . We have two possibilities.
(1) T 1 , and T 2 are vertex disjoint Note that in this case we have n = 6 and therefore |P| = 4 (since P is an optimal ST-partition of K 6 ). But on the other hand, we have |P | 2 + 3 = 5 as T 1 , T 2 ∈ P and at least three vertices of T 1 ∪ T 2 are centers. To see the latter claim, consider the edges e 1 , e 2 , e 3 of K 6 which are shown in below Each of these edges must belong to a triangle or a start in P. But none of them can belong to a triangle as there are no other triangle in P except T 1 and T 2 . So, each of them must belong to a star, and hence one of the endpoints of each of e 1 , e 2 , and e 3 must be the center of a star. So, there are at least three stars in P as these edges are pairwise disjoint. Hence P must have at least 5 elements which contradicts the optimality of P.
(2) If T 1 , and T 2 have a vertex in common, then we have |P | 2 + 2 = 4, as T 1 , T 2 ∈ P , and at least two vertices of T 1 ∪ T 2 are centers. Again to see why the latter claim is true, it is enough to consider the edges e 1 and e 2 which are depicted below and repeat the same argument. So, the size of P is at least four. But, this is again impossible as P is an optimal ST-partition of K 5 which implies |P| = 3.
Case II. Finally, suppose there are at least 3 triangles in P. Then, this implies that no vertex of a triangle is a center of a star. Indeed, if there was a triangle T in P which one of its vertices was a center of a star, then all the other triangles in P except at most one of them is attached to this triangle at x (otherwise removing this vertex would lead to an optimal ST-partition for K n−1 with at least two triangles which would contradict the minimality of n) as shown in below Now, consider the edges e 1 and e 2 of K n as shown below.
At most one of these edges can be covered with that only one possible triangle P which is not attached to x. So, at least one of the end points of e 1 or e 2 must be the center of a star. But then, we would have a triangle with two of its vertices (x and of the endpoints of e 1 or x and of the endpoints of e 2 ) are the center of stars which would contradict Lemma 1. So, all member of P are triangles. Thus, we must have as P is an optimal ST-partition of edges of K n . This equation just has two solutions n = 3 or 4, but on the other hand having at least 3 triangles in P implies n 6 which is again a contradiction. So, we have shown that any optimal ST-partition of K n contains at most one triangle. Moreover, we show that every optimal ST-partition of K n contains exactly one triangle provided that n 3. Indeed, the size of any ST-partition P of K n without a triangle is at least n − 1 as at least one of the endpoints of each edge must be the center of a star. Thus, any optimal ST-partition P of K n where n 3 has exactly one triangle (as |P| = n − 2 for n 3). Corollary 1. Let n 3 be a natural number. For every non-negative integers l and m with l + m = n − 2, and any optimal proper coloring of KG(n, 2), there is a colorful complete tripartite K l,m subgraph in KG(n, 2).
Proof. The assertion is obviously true for n = 3. So, without loss of generality we can assume n 4. Let P be an arbitrary optimal ST-partition of K n . By Theorem 1, P contains exactly one triangle, say T with vertex set {1, 2, 3}. Moreover, no vertex of this triangle is a center of a star. Since otherwise, we could delete this vertex and find a minimal ST-partition for K n−1 without any triangle. Then, this would imply that n − 1 2, which contradicts our assumption. Now, K A,B is the desired subgraph in KG(n, 2) where Above proof reveals that we can have a similar result about the existence of colorful complete tripartite subgraph in KG(n, 2) as well.
Corollary 2. Let n 6 be a natural number. For every integers k, l, m 1 with k + l + m = n − 3, and any optimal proper coloring of KG(n, 2), there is a colorful complete tripartite K k,l,m subgraph in KG(n, 2).
Proof. Again, by Theorem 1, P contains exactly one triangle, say T with vertex set {1, 2, 3} and also as mentioned before no vertex of this triangle can be a center of a star. Now, K A,B,C is the desired subgraph in KG(n, 2) where as each i = 1, 2, 3 is a center of a star and no vertex of T is a center.
Remark. Note that in the previous corollary the assumption k + l + m = n − 3 cannot be replaced with k + l + m = n − 2. To see this, consider the following coloring of KG(n, 2) We can see this coloring as a coloring of edges of the complete graph K n . With having this interpretation in mind, one can check that there is no colorful cycle in K n , i.e., a cycle whose all edges receives different colors. Now, if there was a colorful complete tripartite subgraph K A,B,C in KG(n, 2) where |A| = k, |B| = l, |C| = m with k, l, m 1 and m + l + k = n − 2 , then , as none of A, B, and C form a cycle in K n , we must have | A| k + 1, | B| l + 1, | C| m + 1. Now, since the sets A, B, C are pairwise disjoint, we must have (k+1)+(l+1)+(m+1) n which implies m + l + k n − 3. Then, this would contradict our assumption that m + l + k = n − 2.