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.
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)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。