کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903849 | 1632962 | 2018 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Chromatic index determined by fractional chromatic index
ترجمه فارسی عنوان
شاخص کروماتیک با شاخص کروماتیک کسریتی تعیین می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Given a graph G possibly with multiple edges but no loops, denote by Î the maximum degree, μ the multiplicity, Ïâ² the chromatic index and Ïfâ² the fractional chromatic index of G, respectively. It is known that Îâ¤Ïfâ²â¤Ïâ²â¤Î+μ, where the upper bound is a classic result of Vizing. While deciding the exact value of Ïâ² is a classic NP-complete problem, the computing of Ïfâ² is in polynomial time. In fact, it is shown that if Ïfâ²>Î then Ïfâ²=maxâ¡|E(H)|â|V(H)|/2â, where the maximality is taken over all induced subgraphs H of G. Gupta (1967), Goldberg (1973), Andersen (1977), and Seymour (1979) conjectured that Ïâ²=âÏfâ²â if Ïâ²â¥Î+2, which is commonly referred as Goldberg's conjecture. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: For any positive integer m with mâ¥3, every graph G with Ïâ²>mmâ1Î+mâ3mâ1 satisfies Ïâ²=âÏfâ²â. Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We use an extended form of a Tashkinov tree to show that it is true for mâ¤23. With the same technique, we show that if Ïâ²â¥Î+Î/23 then Ïâ²=âÏfâ²â. The previous best known result is for graphs with Ïâ²>Î+Î/2 obtained by Scheide, and by Chen, Yu and Zang, independently. Moreover, we showthat Goldberg's conjecture holds for graphs G with Îâ¤23 or |V(G)|â¤23.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 85-108
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 85-108
نویسندگان
Guantao Chen, Yuping Gao, Ringi Kim, Luke Postle, Songling Shan,