Fractional and integral colourings (Q1363414)

Let \(G=(V,E)\) be an undirected graph and \(c\) any vector in \(\mathbb{Z}^{V(G)}_+\). Denote by \(\chi(G_c)\) and \(\eta(G_c)\) the chromatic number and fractional chromatic number respectively, of \(G\) with respect to \(c\). In this paper graphs are studied for which \(\chi(G_c)-\lceil\eta(G_c)\rceil\leq 1\). It is shown that for the class of graphs satisfying \(\chi(G_c)=\lceil\eta(G_e)\rceil\) (a class generalizing perfect graphs), an analogue of the duplication lemma does not hold. Also a 2-vertex cut decomposition procedure is described, which is related to the integer decomposition property. This is used to show that \(\chi(G_c)=\lceil\eta(G_c)\rceil\) for series-parallel graphs, and \(\chi(G_c)\leq\lceil\eta(G_c)\rceil+ 1\) for graphs that do not have the 4-wheel as a minor.