The total chromatic number of pseudo-outerplanar graphs
type: Item
instance of: scholarly article
title: The total chromatic number of pseudo-outerplanar graphs
zbMATH Open document ID: 0891.05032
published in: Applied Mathematics. Series B (English Edition)
publication date: 1998-07-08T00:00:00Z
review text: \textit{Zhang Zhongfu}, \textit{Zhang Jianxun} and \textit{Wang Jianfang} [The total chromatic number of some graphs, Sci. Sin., Ser. A 31, No. 12, 1434-1441 (1988; Zbl 0664.05017)] proved that for any outerplanar graph \(G\) with maximum degree \(\Delta (G)\geq 3\), \(\chi_T(G)= \Delta(G)+1\), where \(\chi_T(G)\) is the total chromatic number of \(G\). (A slightly shorter proof of this theorem for the case \(\Delta(G)\geq 4\) can be found in the reviewer's monograph [Total colourings of graphs, Lecture Notes in Mathematics 1623 (1996; Zbl 0839.05001)]). The present authors call a planar graph \(G\) \(i\)-pseudo-outerplanar (resp. \(i\)-pseudo-tree) if \(G\) has an \(i\)-element subset of vertices \(U\) such that \(G-U\) is outerplanar (a tree). They prove: (i) if \(G\) is 1-pseudo-outerplanar, then \(\chi_T(G) \leq\Delta (G) +2\); and (ii) if \(G\) is 1-pseudo-outerplanar with \(\Delta (G)\geq 6\) or \(G\) is a 1-pseudo-tree with \(\Delta(G) \geq 3\), then \(\chi_T(G) =\Delta(G) +1\). Reviewer's remark: (i) follows immediately from the fact that \(\chi_T(G) =\Delta (G)+1\) if \(G\) is outerplanar and a result of M. Behzad which says that if \(G\) is a graph of order at least 3, then for any edge \(e\) of \(G\), we have \(\chi_T(G) \leq\chi_T(G-e)+1\); see \textit{M. Behzad} [The total chromatic number of a graph: A survey, Comb. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 1-8 (1971; Zbl 0221.05062)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1112219
zbMATH Keywords: outerplanar graph
zbMATH Keywords: total chromatic number
author: Weifan Wang
author: Keming Zhang
reviewed by: H. P. Yap
MaRDI profile type: Publication
full work available at URL: s11766-997-0048-1
OpenAlex ID: W2326164481
cites work: The Colour Numbers of Complete Graphs
cites work: Q3097395
cites work: On the total coloring of planar graphs.
cites work: On Total Chromatic Number of a Graph
cites work: Q5564127
cites work: Total colourings of graphs
cites work: Q3815316
DOI: 10.1007/S11766-997-0048-1
description: scientific article; zbMATH DE number 1112219