کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657093 1343714 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposing a planar graph of girth 5 into an independent set and a forest
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Decomposing a planar graph of girth 5 into an independent set and a forest
چکیده انگلیسی

We use a list-color technique to extend the result of Borodin and Glebov that the vertex set of every planar graph of girth at least 5 can be partitioned into an independent set and a set which induces a forest. We apply this extension to also extend Grötzsch's theorem that every planar triangle-free graph is 3-colorable. Let G be a plane graph. Assume that the distance between any two triangles is at least 4. Assume also that each triangle contains a vertex such that this vertex is on the outer face boundary and is not contained in any 4-cycle. Then G has chromatic number at most 3. Note that, in this extension of Grötzsch's theorem an unbounded number of triangles are allowed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 99, Issue 4, July 2009, Pages 674-684