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