全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Strong edge-colouring of sparse planar graphs

Full-Text   Cite this paper   Add to My Lib

Abstract:

A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree $\Delta$ has a strong edge-colouring with at most $4\Delta+4$ colours. We show that $3\Delta+1$ colours suffice if the graph has girth 6, and $4\Delta$ colours suffice if $\Delta\geq 7$ or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133