Skip to main content
added 409 characters in body
Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Take the Kneser graph $K(2k+r,k)$, defined as the graph where the vertices are the $k$-element subsets of $\{1,2,\dots,2k+r\}$, and there is an edge between two vertices if the corresponding sets are disjoint. It is not hard to prove that we can take any $c < \frac{1}{2+\frac{r}{k}}$, but the chromatic number is $r+2$. So the answer to your question is negative.

Remark: The quantity $\rho(G)=\max_{H\subseteq G}\left(\frac{|H|}{\alpha(H)}\right)$ is called the Hall ratio of $G$. It is known that $\rho(G)\le \chi_f(G)\le \chi(G)$, where $\chi_f$ is the fractional chromatic number. The reason why Kneser graphs are natural to bring up in this context is because they are known as a natural example of graphs where $\chi$ is not bounded as a function of $\chi_f$.

Take the Kneser graph $K(2k+r,k)$, defined as the graph where the vertices are the $k$-element subsets of $\{1,2,\dots,2k+r\}$, and there is an edge between two vertices if the corresponding sets are disjoint. It is not hard to prove that we can take any $c < \frac{1}{2+\frac{r}{k}}$, but the chromatic number is $r+2$. So the answer to your question is negative.

Take the Kneser graph $K(2k+r,k)$, defined as the graph where the vertices are the $k$-element subsets of $\{1,2,\dots,2k+r\}$, and there is an edge between two vertices if the corresponding sets are disjoint. It is not hard to prove that we can take any $c < \frac{1}{2+\frac{r}{k}}$, but the chromatic number is $r+2$. So the answer to your question is negative.

Remark: The quantity $\rho(G)=\max_{H\subseteq G}\left(\frac{|H|}{\alpha(H)}\right)$ is called the Hall ratio of $G$. It is known that $\rho(G)\le \chi_f(G)\le \chi(G)$, where $\chi_f$ is the fractional chromatic number. The reason why Kneser graphs are natural to bring up in this context is because they are known as a natural example of graphs where $\chi$ is not bounded as a function of $\chi_f$.

Source Link
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

Take the Kneser graph $K(2k+r,k)$, defined as the graph where the vertices are the $k$-element subsets of $\{1,2,\dots,2k+r\}$, and there is an edge between two vertices if the corresponding sets are disjoint. It is not hard to prove that we can take any $c < \frac{1}{2+\frac{r}{k}}$, but the chromatic number is $r+2$. So the answer to your question is negative.