# zbMATH — the first resource for mathematics

The structure of even factors in claw-free graphs. (English) Zbl 1214.05139
Summary: Recently, Jackson and Yoshimoto proved that every bridgeless simple graph $$G$$ with $$\delta (G)\geq 3$$ has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph $$G$$ of order $$n$$ with $$\delta (G)\geq 3$$ has an even factor with at most $$\{1, \lfloor \frac{2n-2}{7}\rfloor \}$$ components. The upper bound is best possible.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
even factor; claw-free graph; components of an even factor
Full Text:
##### References:
  Fleischner, H., Spanning Eulerian subgraphs, the splitting lemma, and petersen’s theorem, Discrete math., 101, 33-37, (1992) · Zbl 0764.05051  Fujisawa, J.; Xiong, L.; Yoshimoto, K.; Zhang, S., The upper bound of the number of cycles in a 2-factor of a line graph, J. graph theory, 55, 72-82, (2007) · Zbl 1118.05049  Gould, R.; Hynds, E., A note on cycles in 2-factors of line graphs, Bull. ICA., 26, 46-48, (1999) · Zbl 0922.05046  Jackson, B.; Yoshimoto, K., Even subgraphs of bridgeless graphs and 2-factors of line graphs, Discrete math., 307, 2775-2785, (2007) · Zbl 1127.05080  B. Jackson, K. Yoshimoto, Spanning even subgraphs of 3-edge-connected graphs, Preprint · Zbl 1180.05057  Kouider, M.; Vestergaard, P.D., Connected factors in graphs—a survey, Graphs combin., 21, 1-26, (2005) · Zbl 1066.05110  Matthews, M.M.; Sumner, D.P., Longest paths and cycles in $$K_{1, 3}$$-free graphs, J. graph theory, 8, 269-277, (1985) · Zbl 0591.05041  Mckee, T.A., Recharacterizing Eulerian: intimations of new duality, Discrete math., 51, 237-242, (1984) · Zbl 0547.05043  Petersen, J., Die theorie der regulären graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03  West, D.B., Introduction to graph theory, (2001), Prentice Hall Upper Saddle River
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.