کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419254 683763 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On interval representations of graphs
ترجمه فارسی عنوان
درباره بازنمایی بازه ای نمودارها
کلمات کلیدی
عدد فاصله؛ شماره پیگیری؛ تکمیل NP ؛ نمودار مسطح
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The interval number i(G)i(G) of a graph GG is the least integer ii such that GG is the intersection graph of sets of at most ii intervals of the real line. The local track number l(G)l(G) is the least integer ll such that GG is the intersection graph of sets of at most ll intervals of the real line and such that two intervals of the same vertex belong to different components of the interval representation. The track number t(G)t(G) is the least integer tt such that E(G)E(G) is the union of tt interval graphs. We show that the local track number of a planar graph with girth at least 7 is at most 2. We also answer a question of West and Shmoys in 1984 by showing that the recognition of 2-degenerate planar graphs with maximum degree 5 and interval number at most 2 is NP-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 202, 31 March 2016, Pages 30–36
نویسندگان
, , ,