On simultaneous colorings of embedded graphs
type: Item
instance of: scholarly article
title: On simultaneous colorings of embedded graphs
zbMATH Open document ID: 0960.05049
DOI: 10.1016/S0012-365X(00)00064-9
author: Daniel P. Sanders
author: John Maharry
published in: Discrete Mathematics
publication date: 2000-11-20T00:00:00Z
review text: Let a graph \(G\) of maximum degree \(\Delta\) be imbedded in a closed 2-manifold \(S\). The authors use discharging to show that if \(\Delta\) is large relative to the genus of \(S\), then the edge-face chromatic number and vertex-edge-face chromatic number of the imbedding are bounded above by \(\Delta+1\) and \(\Delta+2\), respectively. Both bounds are best possible. Moreover, the vertex-edge chromatic number of the graph is also bounded above by \(\Delta+2\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1533348
zbMATH Keywords: embedded graphs
zbMATH Keywords: genus
zbMATH Keywords: chromatic number
zbMATH Keywords: imbedding
reviewed by: Arthur T. White
MaRDI profile type: Publication
Wikidata QID: Q127878838
full work available at URL: s0012-365x(00)00064-9
OpenAlex ID: W2081511067
description: scientific article; zbMATH DE number 1533348