Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949928 | Discrete Applied Mathematics | 2016 | 5 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yezhou Wu, Dong Ye, Cun-Quan Zhang,