Splitting a graph into disjoint induced paths or cycles.

DOI10.1016/S0166-218X(02)00425-0zbMath1073.68031MaRDI QIDQ1408827

Haiko Müller, Hoàng-Oanh Le, Van Bang Le

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

two-level clustered graphs

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ Extremal values and bounds for the zero forcing number ⋮ Grid representations and the chromatic number ⋮ Induced-path partition on graphs with special blocks ⋮ Reprint of: ``Grid representations and the chromatic number ⋮ Fast-mixed searching and related problems on graphs ⋮ Degree-constrained 2-partitions of graphs ⋮ Induced path factors of regular graphs ⋮ Parameterizing path partitions ⋮ The parameterized complexity landscape of finding 2-partitions of digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Treewidth. Computations and approximations
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Splitting a graph into disjoint induced paths or cycles.