The path partition conjecture is true for claw-free graphs
type: Item
instance of: scholarly article
title: The path partition conjecture is true for claw-free graphs
zbMATH Open document ID: 1121.05092
author: Marietjie Frick
author: Jean E. Dunbar
published in: Discrete Mathematics
publication date: 2007-04-26T00:00:00Z
review text: The detour order of a graph \(G\), denoted \(\tau(G)\), is the order of a longest path in \(G\). A 1983 conjecture states that if \(G\) is a graph and \((a,b)\) is a pair of positive integers such that \(\tau(G)= a+ b\), then the vertex set of \(G\) has a partition \((A,B)\) such that \(\tau(G(A))\leq a\) and \(\tau(G(B))\leq b\). This paper proves this conjecture for the class of claw-free graphs and it also shows that to prove this conjecture it is sufficient to consider the class of 2-connected graphs.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5146824
zbMATH Keywords: path partition conjecture
zbMATH Keywords: longest path
zbMATH Keywords: detour order
zbMATH Keywords: claw-free graphs
reviewed by: Alain Bretto
MaRDI profile type: Publication
full work available at URL: j.disc.2005.11.065
OpenAlex ID: W2035713312
Wikidata QID: Q123283230
cites work: Graphs with not all possible path-kernels
cites work: Q4860774
cites work: A survey of hereditary properties of graphs
cites work: Closure and stable Hamiltonian properties in claw-free graphs
cites work: A path(ological) partition problem
cites work: Partition problems and kernels of graphs
cites work: Q5560916
cites work: Q4943521
cites work: Path partitions and \(P_{n}\)-free sets
cites work: Detour Chromatic Numbers
cites work: Q3309863
cites work: Q5530470
cites work: Q3701351
cites work: On a closure concept in claw-free graphs
cites work: Q4715286
DOI: 10.1016/J.DISC.2005.11.065
Recommended article: Q6090902
Recommended article: Q4494410
Recommended article: The \(k\)-in-a-path problem for claw-free graphs
Recommended article: Q3113764
Recommended article: Path factors in claw-free graphs
Recommended article: The Path Partition Conjecture is true for some generalizations of tournaments
Recommended article: On the path partition of graphs
Recommended article: Vizing's conjecture: A two-thirds bound for claw-free graphs
Recommended article: On the Erdős-Gyárfás conjecture in claw-free graphs
Recommended article: Induced Disjoint Paths in Claw-Free Graphs
description: scientific article; zbMATH DE number 5146824