Geodesic
The existence of path-factor covered graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 5-16 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A spanning subgraph H of a graph G is called a P_≥ k-factor of G if every component of H is isomorphic to a path of order at least k, where k≥2. A graph G is called a P_≥ k-factor covered graph if there is a P_≥ k-factor of G covering e for any e∈ E(G). In this paper, we obtain two special classes of P_≥ 2-factor covered graphs. We also obtain two special classes of P_≥ 3-factor covered graphs. Furthermore, it is shown that these results are all sharp.
Keywords: path-factor, $P_{\geq2}$-factor covered graph, $P_{\geq3}$-factor covered graph, claw-free graph, isolated toughness 
@article{DMGT_2023_43_1_a0,
     author = {Dai, Guowei},
     title = {The existence of path-factor covered graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--16},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a0/}
}
TY  - JOUR
AU  - Dai, Guowei
TI  - The existence of path-factor covered graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 5
EP  - 16
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a0/
LA  - en
ID  - DMGT_2023_43_1_a0
ER  - 
%0 Journal Article
%A Dai, Guowei
%T The existence of path-factor covered graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 5-16
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a0/
%G en
%F DMGT_2023_43_1_a0
Dai, Guowei. The existence of path-factor covered graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 5-16. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a0/

[1] J. Akiyama, D. Avis and H. Era, On a {1,2}-factor of a graph, TRU Math. 16 (1980) 97–102.

[2] J. Akiyama and M. Kano, Factors and factorizations of graphs–-a survey, J. Graph Theory 9 (1985) 1–42. https://doi.org/10.1002/jgt.3190090103

[3] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6. https://doi.org/10.1016/0012-365X(82)90048-6

[4] K. Ando, Y. Egawa, A. Kaneko, K.I. Kawarabayashi and H. Matsuda, Path factors in claw-free graphs, Discrete Math. 243 (2002) 195–200. https://doi.org/10.1016/S0012-365X(01)00214-X

[5] C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Woźniak, Partitioning vertices of 1-tough graphs into paths, Theoret. Comput. Sci. 263 (2001) 255–261. https://doi.org/10.1016/S0304-3975(00)00247-4

[6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982).

[7] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-6

[8] Y. Egawa, M. Furuya and K. Ozeki, Sufficient conditions for the existence of a path-factor which are related to odd components, J. Graph Theory 89 (2018) 327–340. https://doi.org/10.1002/jgt.22253

[9] A. Kaneko, A. Kelmans and T. Nishimura, On packing 3-vertex paths in a graph, J. Graph Theory 36 (2001) 175–197. https://doi.org/10.1002/1097-0118(200104)36:43.0.CO;2-T

[10] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two, J. Combin. Theory Ser. B 88 (2003) 195–218. https://doi.org/10.1016/S0095-8956(03)00027-3

[11] M. Kano, G.Y. Katona and Z. Király, Packing paths of length at least two, Discrete Math. 283 (2004) 129–135. https://doi.org/10.1016/j.disc.2004.01.016

[12] M. Kano, C. Lee and K. Suzuki, Path and cycle factors of cubic bipartite graphs, Discuss. Math. Graph Theory 28 (2008) 551–556. https://doi.org/10.7151/dmgt.1426

[13] K-i. Kawarabayashi, H. Matsuda, Y. Oda and K. Ota, Path factors in cubic graphs, J. Graph Theory 39 (2002) 188–193. https://doi.org/10.1002/jgt.10022

[14] M.D. Plummer, Graph factors and factorization:1985–2003 : A survey, Discrete Math. 307 (2007) 791–821. https://doi.org/10.1016/j.disc.2005.11.059

[15] W.T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314–328. https://doi.org/10.4153/CJM-1952-028-2

[16] H. Wang, Path factors of bipartite graphs, J. Graph Theory 18 (1994) 161–167. https://doi.org/10.1002/jgt.3190180207

[17] J. Yang, Y. Ma and G. Liu, Fractional (g, f)-factors in graphs, Appl. Math. J. Chinese Univ. Ser. A 16 (2001) 385–390.

[18] Q.R. Yu and G.Z. Liu, Graph Factors and Matching Extensions (Springer, Berlin, Heidelberg Press, Beijing, 2009). https://doi.org/10.1007/978-3-540-93052-8

[19] H. Zhang and S. Zhou, Characterizations for P\geq2-factor and P\geq3-factor covered graphs, Discrete Math. 309 (2009) 2067–2076. https://doi.org/10.1016/j.disc.2008.04.022

[20] S.Z. Zhou and J.C. Wu, The existence of P\geq3-factor covered graphs, Discuss. Math. Graph Theory 37 (2017) 1055–1065. https://doi.org/10.7151/dmgt.1974