کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776904 | 1413645 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
NoteFractional strong chromatic index of bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1508-1513
Journal: Discrete Mathematics - Volume 340, Issue 7, July 2017, Pages 1508-1513
نویسندگان
MichaÅ DÄbski,