The total chromatic number of regular graphs whose complement is bipartite
type: Item
instance of: scholarly article
title: The total chromatic number of regular graphs whose complement is bipartite
zbMATH Open document ID: 0794.05028
DOI: 10.1016/0012-365X(94)90255-0
published in: Discrete Mathematics
publication date: 1994-04-04T00:00:00Z
review text: Given a graph \(G= (V,E)\), a total coloring of \(G\) is an assignment of colors to the elements of \(V\cup E\) in such a way that no two adjacent or incident elements receive the same color. The total chromatic number \(\chi''(G)\) is the least number of colors in a total coloring of \(G\). There is an almost 30-years-old conjecture that for a simple graph \(G\) we have \(\Delta+ 1\leq \chi''(G)\leq \Delta+ 2\), where \(\Delta\) is the maximum vertex degree of \(G\). If \(\chi''(G)= \Delta+ 1\) then graph \(G\) is type 1 and if \(\chi''(G)= \Delta+ 2\) then \(G\) is type 2. Deciding the type of \(G\) is NP-complete. In the paper the authors prove the following theorem: Let \(G\) be a regular simple graph of even order \(2n\geq 6\) such that \(\overline G\) is bipartite. Then \(G\) is of type 1 if and only if: (i) \(G\neq K_{2n}\) and (ii) \(\overline G\neq K_{n,n}\) when \(n\) is even.
reviewed by: Marek Kubale
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 540928
zbMATH Keywords: 1-factor
zbMATH Keywords: total coloring
zbMATH Keywords: total chromatic number
zbMATH Keywords: simple graph
zbMATH Keywords: maximum vertex degree
zbMATH Keywords: type
zbMATH Keywords: NP-complete
zbMATH Keywords: regular simple graph
zbMATH Keywords: bipartite
author: J. K. Dugdale
author: A. J. W. Hilton
MaRDI profile type: Publication
cites work: Complementary Graphs and Edge Chromatic Numbers
cites work: Q3832589
cites work: The Total Chromatic Number of Graphs of High Minimum Degree
cites work: Q3984519
cites work: Q3266934
cites work: Partial triple systems and edge colourings
cites work: Recent results on the total chromatic number
cites work: Alternating Hamiltonian circuits in edge-coloured bipartite graphs
cites work: A total-chromatic number analogue of Plantholt's theorem
cites work: The total chromatic number of graphs having large maximum degree
cites work: Q3987044
cites work: An upper bound for the total chromatic number
cites work: Q5799732
cites work: The total coloring of a multigraph with maximal degree 4
cites work: Q5591387
cites work: Q5564127
description: scientific article; zbMATH DE number 540928