{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:35:40Z","timestamp":1725795340561},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079554"},{"type":"electronic","value":"9783319079561"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07956-1_15","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:47:17Z","timestamp":1402418837000},"page":"162-173","source":"Crossref","is-referenced-by-count":2,"title":["Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs"],"prefix":"10.1007","author":[{"given":"Shenwei","family":"Huang","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer Graduate Texts in Mathematics\u00a0vol. 244 (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.46298\/dmtcs.372","volume":"8","author":"A. Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Klembt, T., Mahfud, S.: P 6- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics & Theoretical Computer Science\u00a08, 173\u2013188 (2006)","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/j.ejc.2011.12.008","volume":"34","author":"H.J. Broersma","year":"2013","unstructured":"Broersma, H.J., Fomin, F.V., Golovach, P.A., Paulusma, D.: Three complexity results on coloring P k -free graphs. European Journal of Combinatorics\u00a034, 609\u2013619 (2013)","journal-title":"European Journal of Combinatorics"},{"key":"15_CR4","unstructured":"Chudnovsky, M., Maceli, P., Stacho, J., Zhong, M.: Four-coloring graphs with no induced six-vertex path, and no C 5, personal communication"},{"key":"15_CR5","unstructured":"Chudnovsky, M., Maceli, P., Zhong, M.: Three-coloring graphs with no induced six-edge path I: the triangle-free case (in preparation)"},{"key":"15_CR6","unstructured":"Chudnovsky, M., Maceli, P., Zhong, M.: Three-coloring graphs with no induced six-edge path II: using a triangle (in preparation)"},{"key":"15_CR7","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, Winnipeg, Man., Utilitas Math, pp. 125\u2013157 (1980)"},{"key":"15_CR8","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs (manuscript)"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.dam.2013.12.008","volume":"167","author":"P.A. Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics\u00a0167, 107\u2013120 (2014)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR10","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Closing complexity gaps for coloring problems on H-free graphs. Information and Computation (to appear)"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0012-365X(03)00197-3","volume":"272","author":"S. Gravier","year":"2003","unstructured":"Gravier, S., Ho\u00e0ng, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Mathematics\u00a0272, 285\u2013290 (2003)","journal-title":"Discrete Mathematics"},{"issue":"3-4","key":"15_CR12","doi-asserted-by":"crossref","first-page":"413","DOI":"10.4064\/am-19-3-4-413-441","volume":"XIX","author":"A. Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki Applicationes Mathematicae\u00a0XIX(3-4), 413\u2013441 (1987)","journal-title":"Zastosowania Matematyki Applicationes Mathematicae"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/978-3-642-54423-1_47","volume-title":"LATIN 2014: Theoretical Informatics","author":"P. Hell","year":"2014","unstructured":"Hell, P., Huang, S.: Complexity of coloring graphs without paths and cycles. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol.\u00a08392, pp. 538\u2013549. Springer, Heidelberg (2014)"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"C.T. Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C.T., Kami\u0144ski, M., Lozin, V., Sawada, J., Shu, X.: Deciding k-colorability of P 5-free graphs in p-time. Algorithmica\u00a057, 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-40313-2_49","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S. Huang","year":"2013","unstructured":"Huang, S.: Improved complexity results on k-coloring P t -free graphs. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 551\u2013558. Springer, Heidelberg (2013)"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics\u00a0126, 197\u2013221 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR17","first-page":"139","volume":"62","author":"J. Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J.: Precoloring extension with fixed color bound. Acta Mathematica Universitatis Comenianae\u00a062, 139\u2013153 (1993)","journal-title":"Acta Mathematica Universitatis Comenianae"},{"key":"15_CR18","unstructured":"Lov\u00e1sz, L.: Coverings and coloring of hypergraphs. In: Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., pp. 3\u201312 (1973)"},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J. Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphes. Colloq. Math.\u00a03, 161\u2013162 (1955)","journal-title":"Colloq. Math."},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms\u00a05 (2008)","DOI":"10.1145\/1435375.1435385"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B. Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs - a survey. Graphs Combin.\u00a020, 1\u201340 (2004)","journal-title":"Graphs Combin."},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"15_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.7151\/dmgt.1049","volume":"17","author":"Z. Tuza","year":"1997","unstructured":"Tuza, Z.: Graph colorings with local restrictions - a survey. Discuss. Math. Graph Theory\u00a017, 161\u2013228 (1997)","journal-title":"Discuss. Math. Graph Theory"},{"key":"15_CR24","first-page":"3","volume":"101","author":"V.G. Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors, in Diskret. Analiz., no. 29. Metody Diskret. Anal. v. Teorii Kodov i Shem\u00a0101, 3\u201310 (1976)","journal-title":"Metody Diskret. Anal. v. Teorii Kodov i Shem"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07956-1_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:50:56Z","timestamp":1649335856000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07956-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079554","9783319079561"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07956-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}