View PDF HTML (experimental)

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.

Submission history

From: Bence Csonka [view email]
[v1] Sun, 13 Jul 2025 22:02:27 UTC (16 KB)
[v2] Tue, 21 Jul 2026 09:16:24 UTC (16 KB)