کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657488 1343740 2007 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A special case of Hadwiger's conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A special case of Hadwiger's conjecture
چکیده انگلیسی

We investigate Hadwiger's conjecture for graphs with no stable set of size 3. Such a graph on at least 2t−1 vertices is not t−1 colorable, so is conjectured to have a Kt minor. There is a strengthening of Hadwiger's conjecture in this case, which states that there is a Kt minor in which the preimage of each vertex of Kt is a single vertex or an edge. We prove this strengthened version for graphs with an even number of vertices and fractional clique covering number less than 3. We investigate several possible generalizations and obtain counterexamples for some and improved results from others. We also show that for sufficiently large n, a graph on n vertices with no stable set of size 3 has a minor using only vertices and single edges as preimages of vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 97, Issue 6, November 2007, Pages 1056-1073