کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512609 | 1632458 | 2005 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A generalization of the theorem of Lekkerkerker and Boland
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Each fixed graph H gives rise to a list H-colouring problem. The complexity of list H-colouring problems has recently been fully classified: if H is a bi-arc graph, the problem is polynomial-time solvable, and otherwise it is NP-complete. The proof of this fact relies on a forbidden substructure characterization of bi-arc graphs, reminiscent of the theorem of Lekkerkerker and Boland on interval graphs. In this note we show that in fact the theorem of Lekkerkerker and Boland can be derived from the characterization.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 299, Issues 1â3, 28 August 2005, Pages 113-119
Journal: Discrete Mathematics - Volume 299, Issues 1â3, 28 August 2005, Pages 113-119
نویسندگان
Pavol Hell, Jing Huang,