کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903885 | 1632964 | 2018 | 41 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterizing 4-critical graphs with Ore-degree at most seven
ترجمه فارسی عنوان
مشخص کردن گرافیت های چهارگانه با درجه درجه دوم در بیشتر از 7
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی نمودار، درجه رشته، نمودار 4-بحرانی، روش بالقوه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Kostochka and Yancey's short but beautiful proof for the case k=4 says that if G is a 4-critical graph, then |E(G)|â¥(5|V(G)|â2)/3. We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G, then |E(G)|â¥1.6|V(G)|+.2α(D3(G))â.6, where D3(G) is the graph induced by the degree three vertices of G. As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K4 and Ore compositions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 129, March 2018, Pages 107-147
Journal: Journal of Combinatorial Theory, Series B - Volume 129, March 2018, Pages 107-147
نویسندگان
Luke Postle,