{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:13Z","timestamp":1759637713707,"version":"3.37.3"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"11","funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/G043434\/1"],"award-info":[{"award-number":["EP\/G043434\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Computer Journal"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1093\/comjnl\/bxv039","type":"journal-article","created":{"date-parts":[[2015,6,9]],"date-time":"2015-06-09T03:16:31Z","timestamp":1433819791000},"page":"3074-3088","source":"Crossref","is-referenced-by-count":19,"title":["Narrowing the Complexity Gap for Colouring (<i>C<sub>s<\/sub>, P<sub>t<\/sub><\/i>)-Free Graphs"],"prefix":"10.1093","volume":"58","author":[{"given":"Shenwei","family":"Huang","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2015,6,8]]},"reference":[{"key":"2015102808332004000_58.11.3074.1","doi-asserted-by":"crossref","unstructured":"Huang S. , Johnson M. , Paulusma D. (2014) Narrowing the Complexity Gap for Colouring $(C_s,P_t)$ -Free Graphs. Proc. AAIM 2014, Vancouver, Canada, July 8\u201311. Lecture Notes in Computer Science 8546, pp. 162\u2013173. Springer, Berlin, Heidelberg.","DOI":"10.1007\/978-3-319-07956-1_15"},{"key":"2015102808332004000_58.11.3074.2","unstructured":"Lov\u00e1sz L. (1973) Coverings and Coloring of Hypergraphs. Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, March 5\u20138, pp. 3\u201312. Utilitas Mathematica Publishing, Winnipeg."},{"key":"2015102808332004000_58.11.3074.3","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0540-1"},{"key":"2015102808332004000_58.11.3074.4","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1049"},{"key":"2015102808332004000_58.11.3074.5","doi-asserted-by":"crossref","unstructured":"Golovach P.A. , Johnson M. , Paulusma D. , Song J. (2015) A survey on the computational complexity of colouring graphs with forbidden subgraphs. Manuscript, arXiv:1407.1482v4.","DOI":"10.1002\/jgt.22028"},{"key":"2015102808332004000_58.11.3074.6","unstructured":"Chudnovsky M. , Maceli P. , Stacho J. , Zhong M. (2014) 4-Coloring $P_6$ -free graphs with no induced 5-cycles. Manuscript, arXiv:1407.2487."},{"key":"2015102808332004000_58.11.3074.7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.12.008"},{"key":"2015102808332004000_58.11.3074.8","doi-asserted-by":"crossref","unstructured":"Hell P. , Huang S. (2014) Complexity of Coloring Graphs Without Paths and Cycles. Proc. LATIN 2014, Montevideo, Uruguay, March 31\u2013April 4, Lecture Notes in Computer Science 8392, pp. 538\u2013549. Springer, Berlin, Heidelberg.","DOI":"10.1007\/978-3-642-54423-1_47"},{"key":"2015102808332004000_58.11.3074.9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9197-8"},{"key":"2015102808332004000_58.11.3074.10","doi-asserted-by":"crossref","unstructured":"Huang S. (2013) Improved Complexity Results on $k$ -coloring $P_t$ -free Graphs. Proc. MFCS 2013, Klosterneuburg, Austria, August 26\u201330, Lecture Notes in Computer Science 8087, pp. 551\u2013558. Springer, Berlin, Heidelberg.","DOI":"10.1007\/978-3-642-40313-2_49"},{"key":"2015102808332004000_58.11.3074.11","unstructured":"Chudnovsky M. , Maceli P. , Zhong M. (2014) Three-coloring graphs with no induced seven-vertex path I: the triangle-free case. Manuscript, arXiv:1409.5164."},{"key":"2015102808332004000_58.11.3074.12","unstructured":"Bonomo F. , Schaudt O. , Stein M. (2014) $3$ -Colouring graphs without triangles or induced paths on seven vertices. Manuscript, arXiv:1410.0040."},{"key":"2015102808332004000_58.11.3074.13","unstructured":"Bonomo F. , Chudnovsky M. , Maceli P. , Schaudt O. , Stein M. , Zhong M. (2015) Three-colouring graphs without induced paths on seven vertices I: the triangle-free case. Manuscript."},{"key":"2015102808332004000_58.11.3074.14","unstructured":"Chudnovsky M. , Maceli P. , Zhong M. (2015) Three-coloring graphs with no induced six-edge path II: using a triangle. Manuscript, arXiv:1503.03573."},{"key":"2015102808332004000_58.11.3074.15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.12.008"},{"key":"2015102808332004000_58.11.3074.16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.02.004"},{"key":"2015102808332004000_58.11.3074.17","doi-asserted-by":"crossref","unstructured":"Schaefer T.J. (1978) The Complexity of Satisfiability Problems. Proc. STOC 1978, CA, USA, May 1\u20133, pp. 216\u2013226. ACM, New York.","DOI":"10.1145\/800133.804350"},{"key":"2015102808332004000_58.11.3074.18","first-page":"139","article-title":"Precoloring extension with fixed color bound","volume":"62","author":"Kratochv\u00edl","year":"1993","journal-title":"Acta Math. Univ. Comen."},{"key":"2015102808332004000_58.11.3074.19","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","article-title":"Sur le coloriage des graphes","volume":"3","author":"Mycielski","year":"1955","journal-title":"Colloq. Math."},{"key":"2015102808332004000_58.11.3074.20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"Bondy","year":"2008"},{"key":"2015102808332004000_58.11.3074.21","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"2015102808332004000_58.11.3074.22","doi-asserted-by":"crossref","unstructured":"Kr\u00e1l\u2019 D. , Kratochv\u00edl J. , Tuza Z. , Woeginger G.J. (2001) Complexity of Coloring Graphs Without Forbidden Induced Subgraphs. Proc. WG 2001, Boltenhagen, Germany, June 14\u201316, Lecture Notes in Computer Science 2204, pp. 254\u2013262. Springer, Berlin, Heidelberg.","DOI":"10.1007\/3-540-45477-2_23"},{"key":"2015102808332004000_58.11.3074.23","first-page":"61","article-title":"Coloring edges and vertices of graphs without short or long cycles","volume":"2","author":"Kami\u0144ski","year":"2007","journal-title":"Contrib. Discrete Math."},{"key":"2015102808332004000_58.11.3074.24","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00198-1"},{"key":"2015102808332004000_58.11.3074.25","doi-asserted-by":"crossref","unstructured":"Oum S.-I. (2008) Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms, 5, Article 10, 20 pages.","DOI":"10.1145\/1435375.1435385"},{"key":"2015102808332004000_58.11.3074.26","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00197-3"},{"key":"2015102808332004000_58.11.3074.27","first-page":"413","article-title":"Problems from the world surrounding perfect graphs","volume":"XIX","author":"Gy\u00e1rf\u00e1s","year":"1987","journal-title":"Appl. Math."},{"key":"2015102808332004000_58.11.3074.28","first-page":"125","article-title":"Choosability in graphs","volume":"26","author":"Erd\u00f6s","year":"1979","journal-title":"Congr. Numer."},{"key":"2015102808332004000_58.11.3074.29","unstructured":"Vizing V.G. (1976) Coloring the Vertices of a Graph in Prescribed Colors. In Diskret.Analiz. no. 29, Metody Diskret. Anal.v. Teorii Kodov i Shem, 101, pp. 3\u201310."},{"key":"2015102808332004000_58.11.3074.30","doi-asserted-by":"crossref","first-page":"173","DOI":"10.46298\/dmtcs.372","article-title":"$P_6$ - and triangle-free graphs revisited: structure and bounded clique-width","volume":"8","author":"Brandst\u00e4dt","year":"2006","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/58\/11\/3074\/5156873\/bxv039.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T22:45:18Z","timestamp":1652309118000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article-lookup\/doi\/10.1093\/comjnl\/bxv039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,8]]},"references-count":30,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2015,10,28]]},"published-print":{"date-parts":[[2015,11]]}},"alternative-id":["10.1093\/comjnl\/bxv039"],"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxv039","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published":{"date-parts":[[2015,6,8]]}}}