کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949879 | 1364262 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Threshold-coloring and unit-cube contact representation of planar graphs
ترجمه فارسی عنوان
آشکارسازی آستانه رنگ و مکعب واحد از نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی نمودار، آستانه رنگ آمیزی، نمودارهای پلانار، نمایندگی تماس مکعب واحد،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we study threshold-coloring of graphs, where the vertex colors represented by integers are used to describe any spanning subgraph of the given graph as follows. A pair of vertices with a small difference in their colors implies that the edge between them is present, while a pair of vertices with a big color difference implies that the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. Variants of the threshold-coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and describe a polynomial-time algorithm for another.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 2-14
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 2-14
نویسندگان
Md. Jawaherul Alam, Steven Chaplick, Gašper Fijavž, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev, Jackson Toeniskoetter,