Planar graphs with maximum degree 4 are strongly 19-edge-colorable

Ying Wang, Wai Chee SHIU*, Weifan Wang, Min Chen

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

8 Citations (Scopus)
9 Downloads (Pure)


A strong edge-coloring of a graph is a proper edge-coloring such that edges at distance at most 2 receive different colors. It is known that every planar graph has a strong edge-coloring by using at most 4Δ+4 colors, where Δ denotes the maximum degree of the graph. In this paper, we will show that 19 colors are enough to color a planar graph with maximum degree 4.

Original languageEnglish
Pages (from-to)1629-1635
Number of pages7
JournalDiscrete Mathematics
Issue number6
Publication statusPublished - Jun 2018

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Discharging method
  • Plane graph
  • Strong chromatic index
  • Strong edge-coloring


Dive into the research topics of 'Planar graphs with maximum degree 4 are strongly 19-edge-colorable'. Together they form a unique fingerprint.

Cite this