6
$\begingroup$

Question: What numbers are possible as fractional chromatic numbers?

Clearly, all nonnegative integers are possible, just use the complete graph $K_n$ on $n$ vertices. Also, if we limit our scope to only finite simple graphs, then irrational numbers cannot be fractional chromatic numbers.

For nonintegers, it is clear that fractional chromatic numbers have to be $\geq 2$, because if the graph has an edge, then at least $2n$ colours are needed for the two connected vertices if we assign $n$ colours to a vertex.

There are hence two main questions here:

  1. Can every rational number $\geq 2$ be the fractional chromatic number of a finite simple graph?
  2. Can every number $\geq 2$ be the fractional chromatic number of an infinite simple graph?
$\endgroup$
1

1 Answer 1

2
$\begingroup$

It turns out the answer is yes for both questions.

For 1, using the Kneser graphs would help construct such chromatic numbers, thanks to the observation by @Kyle Miller.

For 2, for irrational $r>2$, consider a strictly increasing sequence of rationals $(r_i)_{i=1}^n$ converging to $r$, where all $r_i\geq2$. Then take a disjoint union of all the Kneser graphs corresponding to each $r_i$. That is, given $r_i=\frac{p_i}{q_i}$, construct the Kneser graph $KG(p_i, q_i)$, and take the disjoint union of all these Kneser graphs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .