The k-piece packing problem

✍ Scribed by David Hartvigsen; Pavol Hell; Jácint Szabó

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 278 KB
• Volume: 52
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20161

✦ Synopsis

Abstract

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [19[, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory