کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5776904 1413645 2017 6 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله
NoteFractional strong chromatic index of bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
NoteFractional strong chromatic index of bipartite graphs
چکیده انگلیسی

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
نویسندگان
,