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.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Fleischner, H., Spanning Eulerian subgraphs, the splitting lemma, and petersen’s theorem, Discrete math., 101, 33-37, (1992) · Zbl 0764.05051
[2] 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
[3] Gould, R.; Hynds, E., A note on cycles in 2-factors of line graphs, Bull. ICA., 26, 46-48, (1999) · Zbl 0922.05046
[4] Jackson, B.; Yoshimoto, K., Even subgraphs of bridgeless graphs and 2-factors of line graphs, Discrete math., 307, 2775-2785, (2007) · Zbl 1127.05080
[5] B. Jackson, K. Yoshimoto, Spanning even subgraphs of 3-edge-connected graphs, Preprint · Zbl 1180.05057
[6] Kouider, M.; Vestergaard, P.D., Connected factors in graphs—a survey, Graphs combin., 21, 1-26, (2005) · Zbl 1066.05110
[7] 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
[8] Mckee, T.A., Recharacterizing Eulerian: intimations of new duality, Discrete math., 51, 237-242, (1984) · Zbl 0547.05043
[9] Petersen, J., Die theorie der regulären graphen, Acta math., 15, 193-220, (1891) · JFM 23.0115.03
[10] 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.