Contraction decomposition in h-minor-free graphs and algorithmic applications
We prove that any graph excluding a fixed minor can have its edges partitioned into a desired number k of color classes such that contracting the edges in any one color class results in a graph of treewidth linear in k. This result is a natural finale to research in contraction decomposition, genera...
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
Association for Computing Machinery (ACM)
2012
|
Online Access: | http://hdl.handle.net/1721.1/73855 https://orcid.org/0000-0003-3803-5703 |