A Generalization of Kneser's Conjecture

Details A Generalization of Kneser's Conjecture A Generalization of Kneser's Conjecture

2009-06-18

arxiv.org/abs/0906.3427v2

Mathematics

Combinatorics

Scientific paper

We investigate some coloring properties of Kneser graphs. A star-free coloring is a proper coloring $c:V(G)\to \Bbb{N}$ such that no path with three vertices may be colored with just two consecutive numbers. The minimum positive integer $t$ for which there exists a star-free coloring $c: V(G) \to \{1,2,..., t\}$ is called the star-free chromatic number of $G$ and denoted by $\chi_s(G)$. In view of Tucker-Ky Fan's lemma, we show that for any Kneser graph ${\rm KG}(n,k)$ we have $\chi_s({\rm KG}(n,k))\geq \max\{2\chi({\rm KG}(n,k))-10, \chi({\rm KG}(n,k))\}$ where $n\geq 2k \geq 4$. Moreover, we show that $\chi_s({\rm KG}(n,k))=2\chi({\rm KG}(n,k))-2=2n-4k+2$ provided that $n \leq {8\over 3}k$. This gives a partial answer to a conjecture of [12]. Also, we conjecture that for any positive integers $n\geq 2k \geq 4$ we have $\chi_s({\rm KG}(n,k))= 2\chi({\rm KG}(n,k))-2$.

Affiliated with

Also associated with

No associations

Rating

A Generalization of Kneser's Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Generalization of Kneser's Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generalization of Kneser's Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-725756