Publication at Faculty of Mathematics and Physics |
2017
Abstract
Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v \mapsto A_v$ to the vertices $v\in V$ such that $A_u$ and $A_v$ are disjoint if and only if $uv\in E$. The smallest such $k$ is called the {\em Kneser rank} of $G$ and denoted by $\fKn(G)$.
As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $00$, $i=1,2$ such that with high probability \[ c_1 n/(\log n)0$ such that $c''_1 n/(\log n)< f_{\min}(G) < c''_2n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.