On improving the edge-face coloring theorem

    Authors

    D. P. Sanders;Y. Zhao

    Abbreviated Journal Title

    Graphs Comb.

    Keywords

    PLANE GRAPHS; Mathematics

    Abstract

    In a previous paper, the authors proved a conjecture of Melnikov that the edges and faces of a plane graph of maximum degree Delta may be simultaneously colored with at most Delta + 3 colors. In this paper, the theorem is reproved with a more direct technique, which also yields improvements. For Delta less than or equal to 5, the theorem is extended to multigraphs. For Delta greater than or equal to 7, it is shown that Delta + 2 colors suffice.

    Journal Title

    Graphs and Combinatorics

    Volume

    17

    Issue/Number

    2

    Publication Date

    1-1-2001

    Document Type

    Article

    Language

    English

    First Page

    329

    Last Page

    341

    WOS Identifier

    WOS:000170097600015

    ISSN

    0911-0119

    Share

    COinS