Přejít k obsahu


Path factors and line graphs

Citace: [] ČADA, R. Path factors and line graphs. Electronic Notes in Discrete Mathematics, 2007, roč. 28, s. 433-436. ISSN: 1571-0653
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Path factors and line graphs
Rok vydání: 2007
Autoři: Roman Čada
Abstrakt CZ: Ando a kol. [K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi, H. Matsuda, Path factors in claw-free graphs, Discr. Math. 243 (2002) 195–200] dokázali, že v souvislém grafu bez K1,3 s minimálním stupněm alespoň d existuje cestový faktor, jehož každá cesta má délku alespoň d. Uvedli hypotézu, že ve 2-souvislém případě má každá cesta délku alespoň 3d+2. Je dokázáno, že tato hypotéza platí pro 2-souvislé hranové grafy.
Abstrakt EN: Ando et al. [K. Ando, Y. Egawa, A. Kaneko, K. Kawarabayashi, H. Matsuda, Path factors in claw-free graphs, Discr. Math. 243 (2002) 195–200] proved that in a connected claw-free graph with minimum degree at least d there is a path factor having each path of length at least d. They conjectured that in a 2-connected case there is a path factor in which each path is of length at least 3d+2. We give a proof of this conjecture for the class of 2-connected line graphs.
Klíčová slova

Zpět

Patička