Title

On Improving The Edge-Face Coloring Theorem

Abstract

In a previous paper, the authors proved a conjecture of Melnikov that the edges and faces of a plane graph of maximum degree Δ may be simultaneously colored with at most Δ + 3 colors. In this paper, the theorem is reproved with a more direct technique, which also yields improvements. For Δ ≤ 5, the theorem is extended to multigraphs. For Δ ≥ 7, it is shown that Δ + 2 colors suffice. © Springer-Verlag 2001.

Publication Date

1-1-2001

Publication Title

Graphs and Combinatorics

Volume

17

Issue

2

Number of Pages

329-341

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/PL00007248

Socpus ID

4344657709 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/4344657709

This document is currently not available here.

Share

COinS