Fractionally colouring total graphs (Q1316649)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Fractionally colouring total graphs
scientific article

    Statements

    Fractionally colouring total graphs (English)
    0 references
    0 references
    0 references
    29 August 1994
    0 references
    To any simple graph \(G=(V,E)\) with maximum vertex degree \(\Delta\) we form a total graph with stable set \(T\) on the vertex set \(V(G) \cup E(G)=F\). It is shown that a feasible solution of the minimum in the linear program \[ \min \left\{ w\bar 1:w \geq 0,\sum_{u \in T} w_ T \geq 1,\;u \in F,\;T \in {\mathcal S} \right\} \] is bounded above by \(\Delta+2\), where \({\mathcal S}\) is the family of total stable sets of \(G\).
    0 references
    colouring
    0 references
    simple graph
    0 references
    total graph
    0 references
    stable set
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references