کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421198 684158 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A sufficient condition for a plane graph with maximum degree 6 to be class 1
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A sufficient condition for a plane graph with maximum degree 6 to be class 1
چکیده انگلیسی

A well-known conjecture of Vizing (the planar graph conjecture) states that every plane graph with maximum degree Δ≥6Δ≥6 is edge ΔΔ-colorable. Vizing himself showed that every plane graph with maximum degree Δ≥8Δ≥8 is edge ΔΔ-colorable. Zhang [L. Zhang, Every graph with maximum degree 7 is of class 1, Graphs Combin. 16 (2000) 467–495] and Sanders and Zhao [D. P. Sanders, Y. Zhao, Planar graphs of maximum degree seven are class 1, J. Combin. Theory Ser. B 83 (2001) 201–212] independently proved that every plane graph with maximum degree 7 is of class 1, i.e., edge 7-colorable. This note shows that every plane graph GG with maximum degree 6 is edge 6-colorable if no vertex in GG is incident with four faces of size 3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 1–2, January 2013, Pages 307–310
نویسندگان
, ,