A generalization of Kneser's conjecture (Q5891501): Difference between revisions
From MaRDI portal
Changed an Item |
Created claim: Wikidata QID (P12): Q123166260, #quickstatements; #temporary_batch_1708296850199 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q123166260 / rank | |||
Normal rank |
Revision as of 02:02, 19 February 2024
scientific article; zbMATH DE number 6023622
Language | Label | Description | Also known as |
---|---|---|---|
English | A generalization of Kneser's conjecture |
scientific article; zbMATH DE number 6023622 |
Statements
A generalization of Kneser's conjecture (English)
0 references
13 April 2012
0 references
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\).''
0 references
graph colorings
0 references
graph of disjoint \(k\)-subsets of an \(n\)-set
0 references
matching
0 references