Claw-decompositions and Tutte-orientations

Janos Barat, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We conjecture that, for each tree T there exists a natural number k(T) such that the following holds: If G is a k(T)-edge-connected graph such that \E(T)\ divides \EG)\, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T=K-1,K-3 (the claw), this holds if and only if there exists a (smallest) natural number k(t) such that every k(t)-edge-connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3-flow conjecture says that k(t)=4. We prove the weaker statement that every 4[ log n]-edge-connected graph with n vertices has an edge-decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge-decomposition into claws. (C) 2006 Wiley Periodicals, Inc.
    Original languageEnglish
    JournalJournal of Graph Theory
    Volume52
    Issue number2
    Pages (from-to)135-146
    ISSN0364-9024
    DOIs
    Publication statusPublished - Jun 2006

    Keywords

    • claw-decompositions
    • orientations
    • triangulations

    Fingerprint Dive into the research topics of 'Claw-decompositions and Tutte-orientations'. Together they form a unique fingerprint.

    Cite this