|  |
| Titel:
|
Graphs with not all possible path-kernels |
| Type:
|
Journal articleJournal article |
| Person(er):
|
Forfatter:
Aldred, Robert
Department of Mathematics and Statistics, University of Otago, Dunedin, New Zealand
Technical University of Denmark
Email:
|
| Uddrag:
|
The Path Partition Conjecture states that the vertices of a graph G with longest path of length c may be partitioned into two parts X and Y such that the longest path in the subgraph of G induced by X has length at most a and the longest path in the subgraph of G induced by Y has length at most b, where a + b = c. Moreover, for each pair a, b such that a + b = c there is a partition with this property. A stronger conjecture by Broere, Hajnal and Mihok, raised as a problem by Mihok in 1985, states the following: For every graph G and each integer k, c greater than or equal to k greater than or equal to 2 there is a partition of V(G) into two parts (K, (K) over bar) such that the subgraph G[K] of G induced by K has no path on more than k - 1 vertices and each vertex in (K) over bar is adjacent to an endvertex of a path on k - 1 vertices in G[K]. In this paper we provide a counterexample to this conjecture. (C) 2004 Elsevier B.V. All rights reserved. |
| Publiceret:
|
in journal: Discrete Mathematics (ISSN: 0012-365X) (DOI: http://dx.doi.org/10.1016/j.disc.2004.02.012), vol: 285, issue: 1-3, pages: 297-300, 2004 |
| DOI:
|
|
|
|