The total chromatic number of pseudo-outerplanar graphs (Q1377186): Difference between revisions

\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)].