Questions tagged [kneser-graph]
For questions relating to the Kneser Graphs, $KG_{n,k}$
7 questions with no upvoted or accepted answers
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
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
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
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
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