کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949928 1440206 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Uniquely forced perfect matching and unique 3-edge-coloring
ترجمه فارسی عنوان
منحصر به فرد تطبیق کامل و منحصر به فرد 3 لبه رنگ را مجبور
کلمات کلیدی
رنگ آمیزی 3 لبه، تطابق، منحصر به فرد 3 لبه رنگ آمیزی، گراف مکعبی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G be a cubic graph with a perfect matching. An edge e of G is a forcing edge if it is contained in a unique perfect matching M, and the perfect matching M is called uniquely forced. In this paper, we show that a 3-connected cubic graph with a uniquely forced perfect matching is generated from K4 via Y→Δ-operations, i.e., replacing a vertex by a triangle, and further a cubic graph with a uniquely forced perfect matching is 2-connected and contains a triangle. Our result generalizes a previous result of Jiang and Zhang (2011). The unique 3-edge-coloring conjecture asserts that a Petersen-minor-free cubic graph with a unique 3-edge-coloring must contain a triangle. Our result verifies that the unique 3-edge-coloring conjecture holds for a subfamily of uniquely 3-edge-colorable cubic graphs, namely cubic graphs with uniquely forced perfect matching.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 215, 31 December 2016, Pages 203-207
نویسندگان
, , ,