کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650629 | 1632449 | 2006 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Berge-keeping operation for graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We prove that a certain simple operation does not create odd holes or odd antiholes in a graph unless there are already some. In order to apply it, we need a vertex whose neighborhood has a coloring where the union of any two color classes is a connected graph; the operation is the shrinking of each of the color classes. Odd holes and antiholes do have such a vertex, and this property of minimal imperfect graphs implies the strong perfect graph theorem through the results of the paper. Conceivably, this property may be a target in the search for a proof of the strong perfect graph theorem different from the monumental achievement of Chudnovsky, Robertson, Seymour, and Thomas.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2582–2592
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2582–2592
نویسندگان
András Sebő,