A total-chromatic number analogue of Plantholt's theorem
type: Item
instance of: scholarly article
title: A total-chromatic number analogue of Plantholt's theorem
zbMATH Open document ID: 0714.05025
DOI: 10.1016/0012-365X(90)90031-C
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: Let \(n\geq 1\), let J be a subgraph of \(K_{2n}\), let \(e=| E(J)|\) and let j be the maximum size of a matching in J. In this paper it is proved that \(\chi_ T(K_{2n}\setminus E(J))=2n+1\) \((=\chi_ T(K_{2n}))\) if and only if \(e+j\leq n-1,\) thus obtaining a total- chromatic number analogue of Plantholt's theorem about the chromatic index of the graph obtained from \(K_{2n+1}\) by removing just a few edges. Under the same hypotheses it is also shown that \(\chi_ T(H)=\Delta (H)+2\) if \(e+j\leq n-1\) and \(\chi_ T(H)=\Delta (H)+1\) if \(n\leq e+j\leq 2n-1,\) where \(H=K_{2n}\setminus E(J).\) A conjecture about related problems is proposed.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4174954
zbMATH Keywords: Behzad conjecture
zbMATH Keywords: edge-colouring
zbMATH Keywords: matching
zbMATH Keywords: total-chromatic number
author: A. J. W. Hilton
MaRDI profile type: Publication
cites work: Q3342598
cites work: Q5799732
cites work: Q5564127
full work available at URL: 0012-365x(90)90031-c
OpenAlex ID: W2074375635
description: scientific article; zbMATH DE number 4174954