کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903059 | 1632401 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
ترجمه فارسی عنوان
برخی از نقاط در تعداد رنگ در فاصله و چرخه فاصله لبه رنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی لبه فاصله، رنگ آمیزی لبه فاصله زمانی، رنگ آمیزی لبه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An intervalt-coloring of a multigraph G is a proper edge coloring with colors 1,â¦,t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic intervalt-coloring of a multigraph G is a proper edge coloring with colors 1,â¦,t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. Denote by w(G) (wc(G)) and W(G) (Wc(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G, respectively. We present some new sharp bounds on w(G) and W(G) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2-connected multigraph with an interval coloring, then W(G)â¤1+|V(G)|2(Î(G)â1). We also give several results towards the general conjecture that Wc(G)â¤|V(G)| for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 627-637
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 627-637
نویسندگان
Carl Johan Casselgren, Hrant H. Khachatrian, Petros A. Petrosyan,