Properties of an Approximability-related Parameter on Circular Complete Graphs

The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H = K k this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs K p / q , where 2 ⩽ p / q ⩽ 3 . The results are extended to K 4 -minor-free graphs. We also consider connections with Šámalʹs work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.