کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8941834 | 1645038 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the precise value of the strong chromatic index of a planar graph with a large girth
ترجمه فارسی عنوان
بر روی مقدار دقیق شاخص کروماتیک قوی یک گراف مسطح با محدوده بزرگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شاخص رنگی قوی، نمودار پلانار، غرق شدن
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A strongk-edge-coloring of a graph G is a mapping from E(G) to {1,2,â¦,k} such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic indexÏsâ²(G) of a graph G is the minimum k for which G has a strong k-edge-coloring. Denote Ï(G)=maxxyâE(G){deg(x)+deg(y)â1}. It is easy to see that Ï(G)â¤Ïsâ²(G) for any graph G, and the equality holds when G is a tree. For a planar graph G of maximum degree Î, it was proved that Ïsâ²(G)â¤4Î+4 by using the Four Color Theorem. The upper bound was then reduced to 4Î, 3Î+5, 3Î+1, 3Î, 2Îâ1 under different conditions for Î and the girth. In this paper, we prove that if the girth of a planar graph G is large enough and Ï(G)â¥Î(G)+2, then the strong chromatic index of G is precisely Ï(G). This result reflects the intuition that a planar graph with a large girth locally looks like a tree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 389-397
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 389-397
نویسندگان
Gerard Jennhwa Chang, Guan-Huei Duh,