کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903885 1632964 2018 41 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterizing 4-critical graphs with Ore-degree at most seven
ترجمه فارسی عنوان
مشخص کردن گرافیت های چهارگانه با درجه درجه دوم در بیشتر از 7
کلمات کلیدی
رنگ آمیزی نمودار، درجه رشته، نمودار 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
نویسندگان
,