Parsimonious Edge-coloring on Surfaces

Sarah-Marie Belcastro

Download full text
(English, 4 pages)

Abstract

We correct a small error in a 1996 paper of Albertson and Haas, and extend their lower bound for the fraction of properly colorable edges of planar subcubic graphs that are simple, connected, bridgeless, and edge-maximal to other surface embeddings of subcubic graphs.

Metrics

  • 55 views
  • 31 downloads

Journal

Electronic Journal of Graph Theory and Applications

The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to ... see more