Fractional matchings, component-factors and edge-chromatic critical graphs

Abstract

The first part of the paper studies star-cycle factors of graphs. It characterizes star-cycle factors of a graph $G$ and proves upper bounds for the minimum number of $K_{1,2}$-components in a $\{K_{1,1},K_{1,2},C_n:n\ge 3\}$-factor of a graph $G$. Furthermore, it shows where these components are located with respect to the Gallai-Edmonds decomposition of $G$ and it characterizes the edges which are not contained in any $\{K_{1,1},K_{1,2},C_n:n\ge 3\}$-factor of $G$. The second part of the paper proves that every edge-chromatic critical graph $G$ has a $\{K_{1,1},K_{1,2},C_n:n\ge 3\}$-factor, and the number of $K_{1,2}$-components is bounded in terms of its fractional matching number. Furthermore, it shows that for every edge $e$ of $G$, there is a $\{K_{1,1},K_{1,2},C_n:n\ge 3\}$-factor $F$ with $e\in E(F)$. Consequences of these results for Vizing's critical graph conjectures are discussed.

final version, 23 pages