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

Ying Wang; Wai Chee Shiu; Weifan Wang; Min Chen

doi:10.1016/j.disc.2018.02.025

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

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

9 Citations (Scopus)

25 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	1629-1635
Number of pages	7
Journal	Discrete Mathematics
Volume	341
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2018.02.025
Publication status	Published - 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

Access to Document

10.1016/j.disc.2018.02.025

Full TextAccepted author manuscript, 249 KB

Cite this

@article{314d4c161af143c59aa077b0b1709c36,

title = "Planar graphs with maximum degree 4 are strongly 19-edge-colorable",

abstract = "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.",

keywords = "Discharging method, Plane graph, Strong chromatic index, Strong edge-coloring",

author = "Ying Wang and Shiu, {Wai Chee} and Weifan Wang and Min Chen",

note = "Funding Information: Research was done while the first author visited the Department of Mathematics, Hong Kong Baptist University in 2017. Research was supported by NSFC grants (Nos. 11771402 ; 11471293 ) and Tianjin Research Program of Application Foundation and Advanced Technology (No. 14JCYBJC43100 ). ",

year = "2018",

month = jun,

doi = "10.1016/j.disc.2018.02.025",

language = "English",

volume = "341",

pages = "1629--1635",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

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

AU - Wang, Ying

AU - Shiu, Wai Chee

AU - Wang, Weifan

AU - Chen, Min

N1 - Funding Information: Research was done while the first author visited the Department of Mathematics, Hong Kong Baptist University in 2017. Research was supported by NSFC grants (Nos. 11771402 ; 11471293 ) and Tianjin Research Program of Application Foundation and Advanced Technology (No. 14JCYBJC43100 ).

PY - 2018/6

Y1 - 2018/6

N2 - 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.

AB - 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.

KW - Discharging method

KW - Plane graph

KW - Strong chromatic index

KW - Strong edge-coloring

UR - http://www.scopus.com/inward/record.url?scp=85044158397&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2018.02.025

DO - 10.1016/j.disc.2018.02.025

M3 - Journal article

AN - SCOPUS:85044158397

SN - 0012-365X

VL - 341

SP - 1629

EP - 1635

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

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

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this