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. / Broersma, Haitze J.; Kriesell, M.; Kriesell, M.; Ryjacek, Z.
Enschede : University of Twente, Department of Applied Mathematics, 1999. 13 p. (Memorandum / Department of Applied Mathematics; No. 1491).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 -