|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|5776904||1413645||2017||6 صفحه PDF||سفارش دهید||دانلود کنید|
The strong chromatic index of a graph G, denoted by sâ²(G), is the minimum possible number of colors in a coloring of the edges of G such that each color class is an induced matching. The corresponding fractional parameter is denoted by sfâ²(G).For a bipartite graph G we have sfâ²(G)â¤1.5ÎG2. This follows as an easy consequence of earlier results Â -Â the fractional variant of Reed's conjecture and the theorem by Faudree, Gyárfás, Schelp and Tuza from 1990. Both these results are tight so it may seem that the bound 1.5ÎG2 is best possible.We break this “1.5 barrier”. We prove that sfâ²(G)â¤1.4762ÎG2+ÎG1.5 for every bipartite graph G. The main part of the proof is a structural lemma regarding cliques in L(G)2.
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1508-1513