The Fractional Haemers Bound of the Mycielski Construction

Abstract

We investigate the effect of the generalized Mycielski construction $M_r(G)$ on the complementary fractional Haemers bound ${\bar{\mathcal{H}}}_f(G;\mathbb{F})$, a parameter that depends on a graph $G$ and a field $\mathbb{F}$. The effect of the Mycielski construction on graph parameters has already been studied for the fractional chromatic number ${\chi }_f$ and the complementary Lovász theta number $\bar{\vartheta }$. Larsen, Propp, and Ullman provided a formula for ${\chi }_f(M_2(G))$ in terms of ${\chi }_f(G)$. This was later generalized by Tardif to ${\chi }_f(M_r(G))$ for any $r$, and Simonyi and the author gave a similar expression for $\bar{\vartheta }(M_2(G))$ in terms of $\bar{\vartheta }(G)$. In this paper, we show that Tardif's formula for the fractional chromatic number remains valid for ${\bar{\mathcal{H}}}_f$ whenever ${\bar{\mathcal{H}}}_f(G;\mathbb{F})$ equals the clique number of $G$. In particular, we provide a general upper bound on ${\bar{\mathcal{H}}}_f(M_r(G);\mathbb{F})$ in terms of ${\bar{\mathcal{H}}}_f(G;\mathbb{F})$ and we prove that this bound is tight whenever ${\bar{\mathcal{H}}}_f(G;\mathbb{F})$ equals the clique number of $G$. Using the bounds, we present a general class of graphs for which the fractional Haemers bound of the generalized Mycielski construction can be determined exactly.

28 pages