### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 13 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 1999 |

### Publication series

Name | Memorandum / Department of Applied Mathematics |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1491 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-05C38
- MSC-05C45
- IR-65680
- METIS-141295
- EWI-3311

### Cite this

*On factors of 4-connected claw-free graphs*. (Memorandum / Department of Applied Mathematics; No. 1491). Enschede: University of Twente, Department of Applied Mathematics.

}

*On factors of 4-connected claw-free graphs*. Memorandum / Department of Applied Mathematics, no. 1491, University of Twente, Department of Applied Mathematics, Enschede.

**On factors of 4-connected claw-free graphs.** / Broersma, Haitze J.; Kriesell, M.; Kriesell, M.; Ryjacek, Z.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - On factors of 4-connected claw-free graphs

AU - Broersma, Haitze J.

AU - Kriesell, M.

AU - Kriesell, M.

AU - Ryjacek, Z.

N1 - Imported from MEMORANDA

PY - 1999

Y1 - 1999

N2 - We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is Hamiltonian, i.e. has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e. graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjecture 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths.

AB - We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is Hamiltonian, i.e. has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e. graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjecture 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths.

KW - MSC-05C38

KW - MSC-05C45

KW - IR-65680

KW - METIS-141295

KW - EWI-3311

M3 - Report

SN - 0169-2690

T3 - Memorandum / Department of Applied Mathematics

BT - On factors of 4-connected claw-free graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -