Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871169 | Discrete Applied Mathematics | 2018 | 4 Pages |
Abstract
We consider the question whether the least number Ï of odd components in a 2-factor is the same as the least number Ïw of odd components in an even factor of a cubic graph. Both invariants appear in the literature under the same name “oddness”. We show that these two invariants are different by constructing graphs G satisfying Ï(G)<Ïw(G)<Ï(G) (where Ï denotes resistance, i.e. the least number of edges that have to be removed from a cubic graph in order to turn it into a 3-edge-colourable graph). In addition, we demonstrate that the difference between any two of those three invariants may be arbitrarily large. Our results imply that if we replace a vertex of a cubic graph with a triangle, then its oddness (Ï) may significantly decrease.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Robert Lukot'ka, Ján Mazák,