On the complete chromatic number of Halin graphs
type: Item
instance of: scholarly article
title: On the complete chromatic number of Halin graphs
zbMATH Open document ID: 0881.05047
DOI: 10.1007/BF02020485
author: Linzhong Liu
author: Zhongfu Zhang
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1997-08-07T00:00:00Z
review text: The complete chromatic number of a plane graph \(G\) is the minimal number \(k\) such that all elements of \(G\) (vertices, edges, and faces) can be coloured with at most \(k\) colours in such a way that any two adjacent or incident elements have different colours. A Halin graph is a planar graph of minimal degree at least 3 which can be obtained from a tree by adding a cycle whose vertex set is the set of all endvertices of the tree. The authors show that the complete chromatic number of a Halin graph equals its maximal degree plus 1 if that maximal degree is at least 6. Their proof consists of an extensive case analysis.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1045902
zbMATH Keywords: complete chromatic number
zbMATH Keywords: plane graph
zbMATH Keywords: colours
zbMATH Keywords: Halin graph
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: A seven-color theorem on the sphere
cites work: The complete chromatic number of some planar graphs
cites work: Q3097395
cites work: Q3715121
full work available at URL: https://doi.org/10.1007/bf02020485
OpenAlex ID: W1992895953
description: scientific article; zbMATH DE number 1045902