Title
Vertex-bipartition method for colouring minor-closed classes of graphs
Abstract
Thomas conjectured that there is an absolute constant c such that for every proper minor-closed class of graphs, there is a polynomial-time algorithm that can colour every G ∈ with at most χ(G) + c colours. We introduce a parameter ρ(), called the degenerate value of , which is defined to be the smallest r such that every G ∈ can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on ), and a part that is r-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 of Kn-minor-free graphs is at most n + 1. These results give rise to P-time approximation algorithms for colouring any graph in these classes within an error of at most 7 and n + 2 of its chromatic number, respectively.
Year
DOI
Venue
2010
10.1017/S0963548310000076
Combinatorics, Probability & Computing
Keywords
Field
DocType
chromatic number,bounded tree-width,planar graph,kn-minor-free graph,minor-closed class,proper minor-closed class,apex vertex,vertex-bipartition method,fixed number,absolute constant c,bounded local tree-width
Approximation algorithm,Discrete mathematics,Degenerate energy levels,Combinatorics,Vertex (geometry),Chordal graph,Clique-sum,Conjecture,Mathematics,Planar graph,Bounded function
Journal
Volume
Issue
ISSN
19
4
0963-5483
Citations 
PageRank 
References 
1
0.38
11
Authors
2
Name
Order
Citations
PageRank
Guoli Ding144451.58
Stan Dziobiak232.14