{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:10:05Z","timestamp":1685571005755},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T00:00:00Z","timestamp":1271808000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,7]]},"abstract":"Thomas conjectured that there is an absolute constantc<\/jats:italic>such that for every proper minor-closed class<\/jats:private-char>of graphs, there is a polynomial-time algorithm that can colour everyG<\/jats:italic>\u2208<\/jats:private-char>with at most \u03c7(G<\/jats:italic>) +c<\/jats:italic>colours. We introduce a parameter \u03c1(<\/jats:private-char>), called the degenerate value of<\/jats:private-char>, which is defined to be the smallestr<\/jats:italic>such that everyG<\/jats:italic>\u2208<\/jats:private-char>can be vertex-bipartitioned into a part of bounded tree-width (the bound depending only on<\/jats:private-char>), and a part that isr<\/jats:italic>-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 \u03c1(<\/jats:private-char>) 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<\/jats:sub><\/jats:italic>-minor-free graphs is at mostn<\/jats:italic>+ 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<\/jats:italic>+ 2 of its chromatic number, respectively.<\/jats:p>","DOI":"10.1017\/s0963548310000076","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T14:11:53Z","timestamp":1271859113000},"page":"579-591","source":"Crossref","is-referenced-by-count":1,"title":["Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs"],"prefix":"10.1017","volume":"19","author":[{"given":"GUOLI","family":"DING","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STAN","family":"DZIOBIAK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,4,21]]},"reference":[{"key":"S0963548310000076_ref19","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1761"},{"key":"S0963548310000076_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.008"},{"key":"S0963548310000076_ref17","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"S0963548310000076_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"S0963548310000076_ref12","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar","year":"2001"},{"key":"S0963548310000076_ref16","unstructured":"[16] Robertson N. and Seymour P. D. Private communication."},{"key":"S0963548310000076_ref11","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1992-076-8"},{"key":"S0963548310000076_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"S0963548310000076_ref9","volume-title":"Ramsey Theory","author":"Graham","year":"1990"},{"key":"S0963548310000076_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"S0963548310000076_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"S0963548310000076_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.001"},{"key":"S0963548310000076_ref6","volume-title":"Graph Theory","author":"Diestel","year":"2000"},{"key":"S0963548310000076_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"S0963548310000076_ref4","first-page":"316","volume-title":"Proceedings of ICALP 2009, Part I","author":"Demaine","year":"2009"},{"key":"S0963548310000076_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"S0963548310000076_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1106-1"},{"key":"S0963548310000076_ref7","first-page":"278","volume-title":"Proc. 11th Annual IEEE Conference on Computational Complexity","author":"Feige","year":"1996"},{"key":"S0963548310000076_ref8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T21:33:11Z","timestamp":1685568791000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000076\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,21]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["S0963548310000076"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000076","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,21]]}}}