کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646637 1342309 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Upper bound on cubicity in terms of boxicity for graphs of low chromatic number
ترجمه فارسی عنوان
محدودیت بالا بر روی cubicity از نظر boxicity برای نمودارهای عدد رنگی کم
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The boxicity (respectively cubicity  ) of a graph GG is the least integer kk such that GG can be represented as an intersection graph of axis-parallel kk-dimensional boxes (respectively kk-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph GG, cub(G)≤box(G)⌈log2α(G)⌉, where α(G)α(G) is the maximum size of an independent set in GG. In this note we show that cub(G)≤2⌈log2χ(G)⌉box(G)+χ(G)⌈log2α(G)⌉, where χ(G)χ(G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G)≤2(box(G)+⌈log2α(G)⌉).Moreover, we show that for every positive integer kk, there exist graphs with chromatic number kk such that for every ϵ>0ϵ>0, the value given by our upper bound is at most (1+ϵ)(1+ϵ) times their cubicity. Thus, our upper bound is almost tight.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 443–446
نویسندگان
, , ,