Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950800 | Information Processing Letters | 2018 | 4 Pages |
Abstract
â¢We study the strong edge colouring of K4-minor-free graphs.â¢We give a tight upper bound for the strong chromatic index of K4-minor-free graphs.â¢A structural lemma is established.â¢Some examples to attain tightness is constructed.
The strong chromatic index Ïsâ²(G) of a graph G is the smallest integer k such that G has a proper edge k-colouring with the condition that any two edges at distance at most 2 receive distinct colours. In this paper, we prove that if G is a K4-minor free graph with maximum degree Îâ¥3, then Ïsâ²(G)â¤3Îâ2. The result is best possible in the sense that there exist K4-minor free graphs G with maximum degree Î such that Ïsâ²(G)=3Îâ2 for any given integer Îâ¥3.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yiqiao Wang, Ping Wang, Weifan Wang,