Coloring Eulerian triangulations of the projective plane
type: Item
instance of: scholarly article
title: Coloring Eulerian triangulations of the projective plane
zbMATH Open document ID: 0995.05050
DOI: 10.1016/S0012-365X(01)00092-9
author: Bojan Mohar
published in: Discrete Mathematics
publication date: 2002-05-21T00:00:00Z
review text: Let \(G\) be an Eulerian triangulation of the projective plane. In this paper it is shown that \(\chi (G)\leq 5\) and \(G\) has a color factor. Moreover, if \(U\) is any color factor of \(G\), then (i) \(\chi (G)=3\) if and only if \(G-U\) is bipartite; (ii) \(\chi (G)=4\) if and only if \(G-U\) is not bipartite and does not contain a quadrangulation of the projective plane; and (iii) \(\chi (G)=5\) if and only if \(G-U\) is not bipartite and contains a quadrangulation of the projective plane. Such a quadrangulation is necessarily nonbipartite. As a corollary it is deduced that there is a polynomial time algorithm to compute the chromatic number of Eulerian triangulations of the projective plane.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1743033
zbMATH Keywords: projective plane
zbMATH Keywords: triangulation
zbMATH Keywords: coloring
zbMATH Keywords: Eulerian graph
zbMATH Keywords: quadrangulation
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00092-9
OpenAlex ID: W1990879687
description: scientific article; zbMATH DE number 1743033