{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T10:45:52Z","timestamp":1784717152916,"version":"3.55.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T00:00:00Z","timestamp":1496188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00493-017-3553-8","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T00:32:30Z","timestamp":1496190750000},"page":"779-801","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":53,"title":["Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices"],"prefix":"10.1007","volume":"38","author":[{"given":"Flavia","family":"Bonomo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria","family":"Chudnovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Maceli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maya","family":"Stein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingxian","family":"Zhong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,31]]},"reference":[{"key":"3553_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"B. Aspvall, M. F. Plass and R. E. Tarjan: A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters\n                           8 (1979), 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"3553_CR2","volume-title":"Algorithmica","author":"E. Camby","year":"2014","unstructured":"E. Camby and O. Schaudt: A new characterization of Pk-free graphs, Algorithmica, 2014. To appear."},{"key":"3553_CR3","volume-title":"4-coloring P6-free graphs with no induced 5-cycles","author":"M. Chudnovsky","year":"2014","unstructured":"M. Chudnovsky, P. Maceli, J. Stacho and M. Zhong: 4-coloring P6-free graphs with no induced 5-cycles, arXiv:1407.2487v1 [cs.DM], July 2014."},{"key":"3553_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd: Matrix multiplication via arithmetic progressions J. Symbolic Computation\n                           9 (1990), 251\u2013280.","journal-title":"J. Symbolic Computation"},{"key":"3553_CR5","first-page":"249","volume":"43","author":"D. Corneil","year":"1984","unstructured":"D. Corneil, Y. Perl and L. Stewart: Cographs: recognition, applications and algorithms, Congressus Numerantium\n                           43 (1984), 249\u2013258.","journal-title":"applications and algorithms, Congressus Numerantium"},{"key":"3553_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K. Edwards","year":"1986","unstructured":"K. Edwards. The complexity of colouring problems on dense graphs, Theoretical Computer Science\n                           43 (1986), 337\u2013343.","journal-title":"Theoretical Computer Science"},{"key":"3553_CR7","first-page":"125","volume":"26","author":"P. Erdos","year":"1979","unstructured":"P. Erdos, A. Rubin and H. Taylor: Choosability in graphs, Congressus Numerantium\n                           26 (1979), 125\u2013157.","journal-title":"Congressus Numerantium"},{"key":"3553_CR8","volume-title":"A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs","author":"P. Golovach","year":"2015","unstructured":"P. Golovach, M. Johnson, D. Paulusma and J. Song: A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs, arXiv:1407.1482v6 [cs.CC], June 2015."},{"key":"3553_CR9","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.ic.2014.02.004","volume":"237","author":"P. Golovach","year":"2014","unstructured":"P. Golovach, D. Paulusma and J. Song: Closing complexity gaps for coloring problems on H-free graphs, Information and Computation\n                           237 (2014), 204\u2013214.","journal-title":"Information and Computation"},{"key":"3553_CR10","volume-title":"Complexity of coloring graphs without paths and cycles","author":"P. Hell","year":"2013","unstructured":"P. Hell and S. Huang: Complexity of coloring graphs without paths and cycles, arXiv:1310.0340v1 [cs.DM], September 2013."},{"key":"3553_CR11","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"C. T. Ho\u00e0ng","year":"2010","unstructured":"C. T. Ho\u00e0ng, M. Kaminski, V. V. Lozin, J Sawada and X. Shu: Deciding k-colorability of P5-free graphs in polynomial time, Algorithmica\n                           57 (2010), 74\u201381.","journal-title":"Algorithmica"},{"key":"3553_CR12","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer: The NP-completeness of edge-coloring, SIAM Journal on Computing\n                           10 (1981), 718\u2013720.","journal-title":"SIAM Journal on Computing"},{"key":"3553_CR13","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-40313-2_49","volume-title":"Proceedings of the International Symposium on Mathematical Foundations of Computer Science 2013","author":"S. Huang","year":"2013","unstructured":"S. Huang: Improved complexity results on k-coloring Pt-free graphs, in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science 2013, volume 7551 of Lecture Notes in Computer Science, 551\u2013558, 2013."},{"key":"3553_CR14","volume-title":"Narrowing the complexity gap for colouring (Cs,Pt)-free graphs","author":"S. Huang","year":"2014","unstructured":"S. Huang, M. Johnson and D. Paulusma: Narrowing the complexity gap for colouring (Cs,Pt)-free graphs, arXiv:1407.1480v1 [cs.CC], July 2014."},{"key":"3553_CR15","first-page":"61","volume":"2","author":"M. Kaminski","year":"2007","unstructured":"M. Kaminski and V. V. Lozin: Coloring edges and vertices of graphs without short or long cycles, Contributions to Discrete Mathematics\n                           2 (2007), 61\u201366.","journal-title":"Contributions to Discrete Mathematics"},{"key":"3553_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"R. Karp: Reducibility among combinatorial problems, in: R. Miller and J. Thatcher, editors, Complexity of Computer Computations, 85\u2013103. Plenum Press, New York, 1972."},{"key":"3553_CR17","first-page":"254","volume-title":"Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science 2001","author":"D. Kr\u00e1l","year":"2001","unstructured":"D. Kr\u00e1l, J. Kratochv\u00edl, Zs. Tuza and G. J. Woeginger: Complexity of coloring graphs without forbidden induced subgraphs, in: M. C. Golumbic, M. Stern, A. Levy, and G. Morgenstern, editors, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science 2001, volume 2204 of Lecture Notes in Computer Science, pages 254\u2013262, 2001."},{"key":"3553_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D. Leven","year":"1983","unstructured":"D. Leven and Z. Galil: NP-completeness of finding the chromatic index of regular graphs, Journal of Algorithms\n                           4 (1983), 35\u201344.","journal-title":"Journal of Algorithms"},{"key":"3553_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F. Maffray","year":"1996","unstructured":"F. Maffray and M. Preissmann: On the NP-completeness of the k-colorability problem for triangle-free graphs, Discrete Mathematics\n                           162 (1996), 313\u2013317.","journal-title":"Discrete Mathematics"},{"key":"3553_CR20","volume-title":"Polynomielle farbungsalgorithmen f\u00fcr Pk-freie graphen","author":"S. Mellin","year":"2002","unstructured":"S. Mellin: Polynomielle farbungsalgorithmen f\u00fcr Pk-freie graphen, Diplomarbeit am Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln, 2002."},{"key":"3553_CR21","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B. Randerath","year":"2004","unstructured":"B. Randerath and I. Schiermeyer: 3-Colorability 2 P for P6-free graphs, Discrete Applied Mathematics\n                           136 (2004), 299\u2013313.","journal-title":"Discrete Applied Mathematics"},{"key":"3553_CR22","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0012-365X(01)00335-1","volume":"251","author":"B. Randerath","year":"2002","unstructured":"B. Randerath, I. Schiermeyer and M. Tewes: Three-colorability and forbidden subgraphs. II: polynomial algorithms, Discrete Mathematics\n                           251 (2002), 137\u2013153.","journal-title":"Discrete Mathematics"},{"key":"3553_CR23","volume-title":"Personal communication","author":"J. Stacho","year":"2014","unstructured":"J. Stacho: Personal communication, 2014."},{"key":"3553_CR24","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1008293.1008294","volume":"5","author":"L. Stockmeyer","year":"1973","unstructured":"L. Stockmeyer: Planar 3-colorability is polynomial complete. ACM SIGACT News\n                           5 (1973), 19\u201325.","journal-title":"ACM SIGACT News"},{"key":"3553_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.7151\/dmgt.1049","volume":"17","author":"Zs. Tuza","year":"1997","unstructured":"Zs. Tuza: Graph colorings with local constraints\u2013a survey, Discussiones Mathematicae. Graph Theory\n                           17 (1997), 161\u2013228.","journal-title":"Discussiones Mathematicae. Graph Theory"},{"key":"3553_CR26","first-page":"3","volume":"29","author":"V. Vizing","year":"1976","unstructured":"V. Vizing: Coloring the vertices of a graph in prescribed colors, Metody Diskretnogo Analiza\n                           29 (1976), 3\u201310.","journal-title":"Metody Diskretnogo Analiza"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-017-3553-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3553-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-017-3553-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,24]],"date-time":"2018-10-24T03:45:10Z","timestamp":1540352710000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-017-3553-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,31]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["3553"],"URL":"https:\/\/doi.org\/10.1007\/s00493-017-3553-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,31]]}}}