The path partition conjecture is true for claw-free graphs (Q878616)

From MaRDI portal
Revision as of 15:43, 30 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
The path partition conjecture is true for claw-free graphs
scientific article

    Statements

    The path partition conjecture is true for claw-free graphs (English)
    0 references
    0 references
    0 references
    26 April 2007
    0 references
    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.
    0 references
    0 references
    path partition conjecture
    0 references
    longest path
    0 references
    detour order
    0 references
    claw-free graphs
    0 references

    Identifiers