Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs
Guoli Ding, Stan Dziobiak · Combinatorics Probability Computing · 2010
Thomas conjectured that there is an absolute constantcsuch that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour everyG∈ with at most χ(G) +ccolours. We introduce a parameter ρ( ), called the degenerate value of , which is defined to be the smallestrsuch that everyG∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that isr-degenerate. Although the existence of one global bound for the degenerate values of all proper minor-closed classes would imply Thomas's conjecture, we prove that the values ρ( ) can be made arbitrarily large. The problem lies in the clique sum operation. As our main result, we show that excluding a planar graph with a fixed number of apex vertices gives rise to a minor-closed class with small degenerate value. As corollaries, we obtain that (i) the degenerate value of every class of graphs of bounded local tree-width is at most 6, and (ii) the degenerate value of the class ofKn-minor-free graphs is at mostn+ 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 andn+ 2 of its chromatic number, respectively.