Simultaneous coloring of edges and faces of plane graphs
type: Item
instance of: scholarly article
title: Simultaneous coloring of edges and faces of plane graphs
zbMATH Open document ID: 0807.05029
DOI: 10.1016/0012-365X(94)90101-5
author: Oleg V. Borodin
published in: Discrete Mathematics
publication date: 1994-05-05T00:00:00Z
review text: The edge-and-face chromatic number \(\chi_{\text{ef}}(G)\) of a plane graph \(G\) is the least number of colors required to color the edges and faces of \(G\) such that every two adjacent or incident of them receive different colors. It is proved that if \(G\) is a plane graph with maximum degree at least 10 then \(\chi_{\text{ef}}(G)\leq \Delta(G)+1\), the bound being sharp. The proof is based on some new generalizations of Kotzig's Theorem on the minimal weight of edges in plane graphs. It is also proved that if \(G\) is a plane graph without separating triangles and \(\Delta(G)\leq 7\) then \(\chi_{\text{ef}}(G)\leq 10\).
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 562580
zbMATH Keywords: simultaneous coloring
zbMATH Keywords: edge-and-face chromatic number
zbMATH Keywords: plane graph
zbMATH Keywords: Kotzig's Theorem
MaRDI profile type: Publication
cites work: Every planar map is four colorable
cites work: The Colour Numbers of Complete Graphs
cites work: Q3679212
cites work: Q3784093
cites work: On the total coloring of planar graphs.
cites work: Q3922703
cites work: Q5615945
cites work: Q5578803
cites work: A seven-color theorem on the sphere
cites work: Q4075398
cites work: Ein Sechsfarbenproblem auf der Kugel
cites work: Q3115603
cites work: Q5564127
cites work: Q4135588
full work available at URL: 0012-365x(94)90101-5
OpenAlex ID: W2041223264
description: scientific article; zbMATH DE number 562580