Strong chromatic index of -degenerate graphs

详细信息    查看全文

• 作者：Tao Wang ; ^{wangtao@henu.edu.cn" class="auth_mail} ; ^{iwangtao8@gmail.com" class="auth_mail}
• 关键词：Strong chromatic index ; kk-degenerate graph ; Minimally 2-connected graph ; Chordless graph
• 刊名：Discrete Mathematics
• 出版年：6 September 2014
• 年：2014
• 卷：330
• 期：Complete
• 页码：17-19
• 全文大小：344 K

文摘

A strong edge coloring   of a graph X14001563&_mathId=si2.gif&_user=111111111&_pii=S0012365X14001563&_rdoc=1&_issn=0012365X&md5=ca2a7adcbd66ca4bef484357da4e2508" title="Click to view the MathML source">Gmi>Gmi> is a proper edge coloring in which every color class is an induced matching. The strong chromatic index  mi>蠂mi><mi>smi>′(<mi>Gmi>) of a graph 142" title="Click to view the MathML source">Gmi>Gmi> is the minimum number of colors in a strong edge coloring of Gmi>Gmi>. In this note, we improve a result by D臋bski et al. (2013) and show that the strong chromatic index of a kmi>kmi>-degenerate graph Gmi>Gmi> is at most (4k&minus;2)⋅螖(G)&minus;2k²+1mi>kmi>&minus;2)⋅<mi>螖mi>(<mi>Gmi>)&minus;2<mi>kmi>2+1. As a direct consequence, the strong chromatic index of a 2$2$-degenerate graph Gmi>Gmi> is at most 6螖(G)&minus;7mi>螖mi>(<mi>Gmi>)&minus;7, which improves the upper bound 10螖(G)&minus;10mi>螖mi>(<mi>Gmi>)&minus;10 by Chang and Narayanan (2013). For a special subclass of 2$2$-degenerate graphs, we obtain a better upper bound, namely if Gmi>Gmi> is a graph such that all of its 3⁺$3^{+}$-vertices induce a forest, then mi>蠂mi><mi>smi>′(<mi>Gmi>)≤4<mi>螖mi>(<mi>Gmi>)&minus;3; as a corollary, every minimally 2$2$-connected graph Gmi>Gmi> has strong chromatic index at most 4螖(G)&minus;3mi>螖mi>(<mi>Gmi>)&minus;3. Moreover, all the results in this note are best possible in some sense.