The conjecture is false

The conjecture is false and it can be seen that this is so by using a computer program. For example $ \gamma_t(Q_6) = 14 $ which is not a power of two.

Alternatively we can argue as follows. For any graph $ G $ we clearly have $$ \gamma_t(G) \leq 2 \gamma(G).$$ Now the bound by Alon and Spencer states $$\gamma(G) \leq  \frac{1+\log({\delta(G)+1)}}{1+\delta(G)}|V(G)|.$$ In particular this implies that for any constant $ k > 0 $ and large enough $ n $ we have $$\gamma_t(Q_n) \leq 2^{n-k}.$$

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options