2025/07/13 by Bence Csonka, Csonka, Bence
#math.CO
paper · pdf · doi:10.48550/arxiv.2507.09811
We investigate the effect of the generalized Mycielski construction Mr(G) on the complementary fractional Haemers bound Hf(G; \mathbbF), a parameter that depends on a graph G and a field \mathbbF. The effect of the Mycielski construction on graph parameters has already been studied for the fractional chromatic number χf and the complementary Lovász theta number ϑ. Larsen, Propp, and Ullman provided a formula for χf(M2(G)) in terms of χf(G). This was later generalized by Tardif to χf(Mr(G)) for any r, and Simonyi and the author gave a similar expression for ϑ(M2(G)) in terms of ϑ(G). In this paper, we show that Tardif's formula for the fractional chromatic number remains valid for Hf whenever Hf(G; \mathbbF) equals the clique number of G. In particular, we provide a general upper bound on Hf(Mr(G); \mathbbF) in terms of Hf(G;\mathbbF) and we prove that this bound is tight whenever Hf(G; \mathbbF) 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.