Leírás
Kneser graphs ${\rm KG}(n,k)$ are defined for every pair of positive integers $n,k$ satisfying $n\ge 2k$. Their vertex set consists of the $k$-element subsets of $[n]$, two of which are adjacent if they are disjoint. The chromatic number of ${\rm KG}(n,k)$ is $n-2k+2$ and its fractional chromatic number is $n/k$. Generally, Kneser graphs are not vertex-critical for any of those parameters.
Schrijver graphs ${\rm SG}(n,k)$ are vertex-critical subgraphs of Kneser graphs for the chromatic number. They also share the value of their fractional chromatic number but Schrijver graphs are not critical for that either.
In this talk, we present an induced subgraph of every Schrijver graph ${\rm SG}(n,k)$ that is vertex-critical with respect to the fractional chromatic number. This subgraph is isomorphic with the circular complete graph $K_{n'/k'}$, where $\frac{n}{k} = \frac{n'}{k'}$ and $gcd(n',k') = 1$. We also characterize the critical edges within this subgraph.
-
Az eredmény Simonyi Gáborral közös.