Originator: Douglas West (presented by Lale Özkahya - REGS 2009)
Definitions: A graph is degree-splittable (or just splittable) if it decomposes into two graphs having identical degree lists, plus one extra edge when the total number of edges is odd.
Background: Analogous problems for isomorphic decomposition motivate our study. Decomposing complete graphs into isomorphic complete subgraphs is the fundamental problem of design theory. Generalizations to graphs begin with decompositions of complete graphs into cycles of fixed lengths and with the famous conjecture of Ringel that the complete graph with 2m+1 vertices decomposes into isomorphic copies of any tree with m edges.
In [CÖW], it is shown that all regular graphs are degree-splittable. In fact, a simple argument using an Eulerian circuit in a supergraph shows that a graph is degree-splittable if it has an even number of vertices of each odd degree. [CÖW] also shows that all caterpillars of degree at most 4 are degree-splittable. For the remaining caterpillars some necessary or sufficient conditions are given.
Conjecture: The degree-split problem for graphs is NP-complete.
Comment: Perhaps in fact the problem is NP-complete when restricted to trees.
References:
[CÖW] J. Choi, L. Özkahya, D. B. West,
Degree-Splittability of Regular Multigraphs and Caterpillars,
manuscript.