Fractional and integral colourings (Q1363414)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fractional and integral colourings |
scientific article |
Statements
Fractional and integral colourings (English)
0 references
5 January 1998
0 references
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.
0 references
integral colourings
0 references
fractional chromatic number
0 references
decomposition
0 references