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
    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
    0 references

    Identifiers