کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949967 1440208 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On incidence coloring conjecture in Cartesian products of graphs
ترجمه فارسی عنوان
بر فرض هنجاری رنگ آمیزی در محصولات دکارتی گراف
کلمات کلیدی
رنگ آمیزی بروز، ضرب دکارتی، هومومورفیسم موضعی تزریقی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An incidence in a graph G is a pair (v,e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v,e) and (u,f) are adjacent if at least one of the following holds: (a)v=u, (b)e=f, or (c)vu∈{e,f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most Δ(G)+2 colors are needed for an incidence coloring of any graph G. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph G for which G admits an incidence coloring with at most Δ(G)+2 colors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 93-100
نویسندگان
, , ,