Partitioning powers of traceable or Hamiltonian graphs

DOI10.1016/j.tcs.2013.10.016zbMath1305.05185OpenAlexW1965792160MaRDI QIDQ391776

Jakub Przybyło, Mariusz Woźniak, Julien Bensmail, Olivier Baudon

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.10.016

zbMATH Keywords

Hamiltonian grapharbitrarily partitionable graphpower of a graphtraceable graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (8)

Dense on-line arbitrarily partitionable graphs ⋮ Dense arbitrarily partitionable graphs ⋮ Unnamed Item ⋮ Arbitrary partitionability of product graphs ⋮ On three polynomial kernels of sequences for arbitrarily partitionable graphs ⋮ Partitioning the Cartesian product of a tree and a cycle ⋮ On the complexity of partitioning a graph into a few connected subgraphs ⋮ Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for four-partitioning four-connected planar graphs
• A linear algorithm for bipartition of biconnected graphs
• Decomposing trees with large diameter
• Packing closed trails into dense graphs.
• Decomposable trees: A polynomial algorithm for tripodes
• Dense arbitrarily vertex decomposable graphs
• A degree bound on decomposable trees
• On arbitrarily vertex decomposable trees
• Recursively arbitrarily vertex-decomposable suns
• Arbitrarily vertex decomposable caterpillars with four or five leaves
• A homology theory for spanning tress of a graph
• Decomposition of Complete Bipartite Even Graphs into Closed Trails

This page was built for publication: Partitioning powers of traceable or Hamiltonian graphs