On simultaneous edge-face colorings of plane graphs
type: Item
instance of: scholarly article
title: On simultaneous edge-face colorings of plane graphs
zbMATH Open document ID: 0902.05024
author: Daniel P. Sanders
author: X. Zhao
published in: Combinatorica
publication date: 1998-11-23T00:00:00Z
review text: It is proved that the edges and faces of a plane graph may be simultaneously colored with at most \(\Delta +3\) colors, so that adjacent and incident elements receive different colors, where \(\Delta\) is the maximum degree of the graph. The result is tight, since an odd cycle requires that many colors. This settles a conjecture of Melnikov. It is also shown that if \(\Delta \geq 8\) then it is sufficient to use \(\Delta +2\) colors. The proof uses the four color theorem and Vizing's theorem.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1226326
zbMATH Keywords: plane graph
zbMATH Keywords: graph coloring
MaRDI profile type: Publication
Recommended article: Simultaneous coloring of edges and faces of plane graphs
Recommended article: Simultaneously colouring the edges and faces of plane graphs
Recommended article: Q3487364
Recommended article: Q3360218
Recommended article: Q4701960
Recommended article: Q3784093
Recommended article: Edge-coloring of plane multigraphs with many colors on facial cycles
Recommended article: On the simultaneous edge coloring of graphs
Recommended article: Edge-face coloring of 2-connected plane graphs
Recommended article: Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
description: scientific article; zbMATH DE number 1226326