Article ID Journal Published Year Pages File Type
4949928 Discrete Applied Mathematics 2016 5 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,