Large Even Factors of Graphs

Series:
Graph Theory Seminar
Thursday, February 9, 2017 - 15:05
1 hour (actually 50 minutes)
Location:
Skiles 005
,
Center for Discrete Mathematics, Fuzhou University
Organizer:
A spanning subgraph $F$ of a graph $G$ iscalled an even factor of $G$ if each vertex of $F$ has even degreeat least 2 in $F$. It was proved that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)$, which is best possible. Recently, Cheng et al.extended the result by considering vertices of degree 2. They provedthat if a graph $G$ has an even factor, then it has an even factor$F$ with $|E(F)|\geq {4\over 7}(|E(G)| + 1)+{1\over 7}|V_2(G)|$,where $V_2(G)$ is the set of vertices of degree 2 in $G$. They alsogave examples showing that the second coefficient cannot be largerthan ${2\over 7}$ and conjectured that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)+ {2\over 7}|V_2(G)|$. We note that the conjecture isfalse if $G$ is a triangle. We confirm the conjecture for all graphson at least 4 vertices. Moreover, if $|E(H)|\leq {4\over 7}(|E(G)| +1)+ {2\over 7}|V_2(G)|$ for every even factor $H$ of $G$, then everymaximum even factor of $G$ is a 2-factor in which each component isan even circuit.