Fractional total colouring
type: Item
instance of: scholarly article
title: Fractional total colouring
zbMATH Open document ID: 0731.05018
DOI: 10.1016/0166-218X(90)90073-L
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: The total colouring problem of a graph G is to colour all vertices and edges of G with minimum number of colours in such a way that no two adjacent or incident vertices or edges receive the same colour. \textit{Behzad} conjectures in 1965 that a simple graph G can always be totally coloured using two more colours than the maximum degree \(\Delta\) (G) of vertices in G. If the conjecture is true, then the total colouring number of a graph is always equal to either \(\Delta (G)+1\), or \(\Delta (G)+2\). There is an equivalent integer programming formulation. The author proves that the linear programming relaxation of this integer programming has its fractional value bounded between \(\Delta (G)+1\) and \(\Delta (G)+2\). This result gives a proof of a weakening of the mentioned Behzad's conjecture.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C90
zbMATH DE Number: 4208093
zbMATH Keywords: total colouring
zbMATH Keywords: integer programming
zbMATH Keywords: linear programming relaxation
author: Jennifer K. Ryan
MaRDI profile type: Publication
cites work: Q5625208
cites work: The Colour Numbers of Complete Graphs
cites work: Q5422499
cites work: Nombre chromatique total du joint d'un ensemble stable par un cycle
cites work: Q3701198
cites work: On Total Chromatic Number of a Graph
description: scientific article; zbMATH DE number 4208093