Petersen Cores and the Oddness of Cubic Graphs |
| |
| Authors: | Ligang Jin Eckhard Steffen |
| |
| Institution: | 1. PADERBORN INSTITUTE FOR ADVANCED STUDIES IN, COMPUTER SCIENCE AND ENGINEERING AND INSTITUTE FOR MATHEMATICS, PADERBORN UNIVERSITY, GERMANYSupported by Deutsche Forschungsgemeinschaft (DFG) grant STE 792/2‐1.;2. PADERBORN INSTITUTE FOR ADVANCED STUDIES IN, COMPUTER SCIENCE AND ENGINEERING AND INSTITUTE FOR MATHEMATICS, PADERBORN UNIVERSITY, GERMANY |
| |
| Abstract: | Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let  be the set of edges contained in precisely i members of the k 1‐factors. Let  be the smallest  over all lists of k 1‐factors of G. We study lists by three 1‐factors, and call  with  a  ‐core of G. If G is not 3‐edge‐colorable, then  . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if  , then  is an upper bound for the girth of G. We show that  bounds the oddness  of G as well. We prove that  . If  , then every  ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with  . On the other hand, the difference between  and  can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer  , there exists a bridgeless cubic graph G such that  . |
| |
| Keywords: | cubic graphs snarks perfect matchings covers oddness |
|
|
be the set of edges contained in precisely i members of the k 1‐factors. Let 
be the smallest 
over all lists of k 1‐factors of G. We study lists by three 1‐factors, and call 
with 
a 
‐core of G. If G is not 3‐edge‐colorable, then 
. In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if 
, then 
is an upper bound for the girth of G. We show that 
bounds the oddness 
of G as well. We prove that 
. If 
, then every 
‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with 
. On the other hand, the difference between 
and 
can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer 
, there exists a bridgeless cubic graph G such that 
.