کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650629 1632449 2006 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A Berge-keeping operation for graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A Berge-keeping operation for graphs
چکیده انگلیسی

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
نویسندگان
,