Decomposing graphs into paths of fixed length (Q2448964): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q56926560, #quickstatements; #temporary_batch_1712101902020
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Small degree out‐branchings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Claw‐decompositions and tutte‐orientations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perfect path double covers of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3097395 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded degree spanning trees (extended abstract) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4342632 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimum partition of a matroid into independent subsets / rank
 
Normal rank
Property / cites work
 
Property / cites work: P4-decompositions of regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3807237 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On partitioning the edges of graphs into connected subgraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: On some connectivity properties of Eulerian graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Reduction Method for Edge-Connectivity in Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2726740 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edge-Disjoint Spanning Trees of Finite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph decomposition with applications to subdivisions and path systems modulo <i>k</i> / rank
 
Normal rank
Property / cites work
 
Property / cites work: Girth in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edge-decompositions of highly connected graphs into paths / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decompositions of highly connected graphs into paths of length 3 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The weak 3-flow conjecture and the weak circular flow conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Problem of Decomposing a Graph into <i>n</i> Connected Factors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4111952 / rank
 
Normal rank

Latest revision as of 11:22, 8 July 2024

scientific article
Language Label Description Also known as
English
Decomposing graphs into paths of fixed length
scientific article

    Statements

    Decomposing graphs into paths of fixed length (English)
    0 references
    0 references
    5 May 2014
    0 references
    The paper addresses the following conjecture of Barát and Thomassen: For each tree \(T\) there is a natural number \(k = k(T)\) such that any graph \(G\) that is \(k\)-edge connected with \(| E(T)| \) dividing \(| E(G)| \) can be decomposed into edge disjoint copies of the tree \(T\). This conjecture is verified for any tree \(P\) that is a path of length \(p\) a power of \(2\). The proof involves vertex colorings and multi-edge-colorings of a multi-graph \(G\) with edge-connectivity at least \(\alpha(p, m)\), where each edge has at most \(m\) colors and no vertex sees a color more than once.
    0 references
    paths
    0 references
    edge connectivity
    0 references
    path decomposition
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references