A generalization of Kneser's conjecture (Q5891501): Difference between revisions

The author investigates some coloring properties of Kneser graphs. For positive integers \(n\) and \(k\), where \(n\geq 2k\), the Kneser graph \(kG(n,k)\) is the graph whose vertex set is the set of \(k\)-subsets of \(\{1,2,\dots, n\}\), where two vertices are adjacent if and only if the corresponding subsets are disjoint. \textit{M. Kneser} [``Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen,'' Math. Z. 61, 429--434 (1955; Zbl 0064.04305)] conjectured that the chromatic number \(\chi(kG(n,k))\) is equal to \(n-2k+2\). This conjecture was proved by \textit{L. Lovász}, [``Kneser's conjecture, chromatic number, and homotopy,'' J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)]. I will now quote from the author's abstract: ``A semi-matching coloring of a graph \(G\) is a proper coloring \(c: V(G)\to\mathbb{N}\) such that for any two consecutive colors, the edges joining the colors form a matching. The minimum positive integer \(t\) for which there exists a semi-matching coloring \(c: V(G)\to\{1,2,\dots, t\}\) is called the semi-matching chromatic number of \(G\) and denoted by \(\chi_m(G)\). In view of Tucker K. Fan's lemma [\textit{K. Fan's}, ``A generalization of Tucker's combinatorial lemma with topological applications,'' Ann. Math. (2) 56, 431--437 (1952; Zbl 0047.42004)], we show that \[ \chi_m(KG(n, k))= 2\chi(KG(n, k))= 2= 2n-4k+ 2 \] provided that \(n\leq{k\over 3}\). This gives a partial answer to a conjecture of \textit{B. Omoomi} and \textit{A. Pourmiri} [``Local coloring of Kneser graphs,'' Discrete Math. 308, No. 24, 5922--5927 (2008; Zbl 1213.05096)]. Moreover, for any Kneser graph \(KG(n, k)\), we show that \[ \chi_m(KG(n, k))\geq\max\{2\chi(KG(n, k))-10, \chi(KG(n, k))\}, \] where \(n\geq 2k\geq 4\). Also, for \(n\geq 2k\geq 4\), we conjecture that \(\chi_m(KG(n, k))= 2\chi(KG(n, k)) - 2\).''