Questions tagged [kneser-graph]
For questions relating to the Kneser Graphs, $KG_{n,k}$
13 questions
6
votes
0
answers
111
views
What is the largest subgraph of the Kneser graph which has a small chromatic number?
While trying to characterize constraint satisfaction problems which can be solved by the Linear Programming relaxation, I've run into a few perplexing puzzles related to the existence of certain ...
- 8,688
0
votes
0
answers
61
views
Clique sizes of generalized Kneser graphs
Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...
- 2,089
0
votes
0
answers
65
views
Cycles in Kneser graphs with three vertices forming triangles
Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...
- 2,089
0
votes
0
answers
183
views
Covering discrete triangle with generalized knight jumps
Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...
- 91
0
votes
1
answer
81
views
Line graphs of complete hypergraphs as complement of Kneser graphs
Since the Johnson graph/triangular graph $J(n,2)$ is the complement of the Kneser graph $K(n,2)$, which is also incidentally the line graph of the complete graph $K_n$, I thought whether the same can ...
- 2,089
1
vote
1
answer
205
views
Chromatic number or independence number of the generalized Kneser Graph
For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...
- 135
3
votes
0
answers
214
views
Clique cover number of a generalized Kneser graph $K(n,4,2)$
Recently I attacked this combinatorial question. The value of $m(n)$ introduced in it equals to a clique cover number
of a generalized Kneser graph $KG_{n,4,1}=K(n,4,2)$ (or the chromatic number of ...
- 5,409
2
votes
1
answer
275
views
Independent sets in complement of Kneser graphs
Intuition strongly suggests that there exist $\left\lfloor\frac{\binom{n}{k}}{\lfloor\frac{n}{k}\rfloor}\right\rfloor$ independent sets in the complement of a Kneser graph each having $\lfloor\frac{...
- 2,089
4
votes
0
answers
116
views
Faithful Orthogonality Dimension of Kneser Graphs
Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined ...
- 211
4
votes
2
answers
408
views
Simpler combinatorial proof for special case of Kneser's conjecture
Kneser's conjecture states that the chromatic number of the Kneser graph $KG(n,k)$ is $n-2k+2$. A simple proof using topological methods was given by Bárány, and an involved combinatorial proof by ...
- 1,209
1
vote
1
answer
80
views
Variant of Kneser hypergraph with elements appearing more than once
A Kneser hypergraph is a hypergraph with the vertices being the subsets of $M=\{1,2,\dots,m\}$ of size $l$ and the edges being the collections of size $r$ of these subsets such that any two subsets ...
- 277
4
votes
2
answers
411
views
What is the independence number of this graph which is a generalization of a Kneser graph?
Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two ...
- 147
11
votes
0
answers
243
views
Is there a Ramsey theory for Kneser graphs?
Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
- 18.7k