Fractionally colouring total graphs
type: Item
instance of: scholarly article
title: Fractionally colouring total graphs
zbMATH Open document ID: 0795.05056
DOI: 10.1007/BF01303515
author: K. Kilakos
author: Bruce Reed
published in: Combinatorica
publication date: 1994-08-29T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 522714
zbMATH Keywords: colouring
zbMATH Keywords: simple graph
zbMATH Keywords: total graph
zbMATH Keywords: stable set
Wikidata QID: Q56390752
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Anti-blocking polyhedra
cites work: An upper bound for the total chromatic number
cites work: Fractional total colouring
cites work: On Total Chromatic Number of a Graph
description: scientific article; zbMATH DE number 522714