Partitioning powers of traceable or Hamiltonian graphs

DOI10.1016/j.tcs.2013.10.016zbMath1305.05185MaRDI 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 graph; arbitrarily partitionable graph; power of a graph; traceable graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C45: Eulerian and Hamiltonian graphs

Related Items

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