{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T02:33:23Z","timestamp":1776911603088,"version":"3.51.2"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,5,17]],"date-time":"2018-05-17T00:00:00Z","timestamp":1526515200000},"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":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00373-018-1905-9","type":"journal-article","created":{"date-parts":[[2018,5,17]],"date-time":"2018-05-17T09:49:08Z","timestamp":1526550548000},"page":"677-692","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["On the Chromatic Number of (\n                \n                  \n                \n                $$P_6$$\n                \n                  \n                    \n                      P\n                      6\n                    \n                  \n                \n              , Diamond)-Free Graphs"],"prefix":"10.1007","volume":"34","author":[{"given":"T.","family":"Karthick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suchismita","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,17]]},"reference":[{"key":"1905_CR1","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1016\/j.jctb.2007.12.006","volume":"98","author":"L Addario-Berry","year":"2008","unstructured":"Addario-Berry, L., Chudnovsky, M., Havet, F., Reed, B., Seymour, P.: Bisimplicial vertices in even-hole-free graphs. J. Combin. Theory Ser. B 98, 1119\u20131164 (2008)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"1905_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00373-017-1870-8","volume":"34","author":"AP Bharathi","year":"2018","unstructured":"Bharathi, A.P., Choudum, S.A.: Colouring of \n                    \n                      \n                    \n                    $$P_2\\cup P_3$$\n                    \n                      \n                        \n                          \n                            P\n                            2\n                          \n                          \u222a\n                          \n                            P\n                            3\n                          \n                        \n                      \n                    \n                  -free graphs. Graphs Combin. 34(1), 97\u2013107 (2018)","journal-title":"Graphs Combin."},{"key":"1905_CR3","doi-asserted-by":"crossref","unstructured":"Blanche, A., Dabrowski, K. K., Johnson, M., Paulusma, D.: Hereditary graph Classes: when the complexities of colouring and clique cover coincide. \n                    arXiv:1607.06757v3\n                    \n                   (2017)","DOI":"10.1002\/jgt.22431"},{"key":"1905_CR4","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.dam.2011.10.031","volume":"160","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V., Maffray, F.: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Disc. Appl. Math. 160, 471\u2013478 (2012)","journal-title":"Disc. Appl. Math."},{"key":"1905_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0166-218X(01)00277-3","volume":"120","author":"S Brandt","year":"2002","unstructured":"Brandt, S.: Triangle-free graphs and forbidden subgraphs. Disc. Appl. Math. 120, 25\u201333 (2002)","journal-title":"Disc. Appl. Math."},{"key":"1905_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2011.10.005","volume":"414","author":"HJ Broersma","year":"2012","unstructured":"Broersma, H.J., Golovach, P.A., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoret. Comput. Sci. 414, 9\u201319 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1905_CR7","doi-asserted-by":"publisher","first-page":"3398","DOI":"10.1016\/j.disc.2010.08.005","volume":"310","author":"SA Choudum","year":"2010","unstructured":"Choudum, S.A., Karthick, T.: Maximal cliques in \n                    \n                      \n                    \n                    $$P_2 \\cup P_3, C_4$$\n                    \n                      \n                        \n                          \n                            P\n                            2\n                          \n                          \u222a\n                          \n                            P\n                            3\n                          \n                          ,\n                          \n                            C\n                            4\n                          \n                        \n                      \n                    \n                  -free graphs. Disc. Math. 310, 3398\u20133403 (2010)","journal-title":"Disc. Math."},{"issue":"4","key":"1905_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/jgt.20212","volume":"54","author":"SA Choudum","year":"2007","unstructured":"Choudum, S.A., Karthick, T., Shalu, M.A.: Perfect coloring and linearly \n                    \n                      \n                    \n                    $$\\chi $$\n                    \n                      \n                        \u03c7\n                      \n                    \n                  -bound \n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. J. Graph Theory 54(4), 293\u2013306 (2007)","journal-title":"J. Graph Theory"},{"key":"1905_CR9","first-page":"1774","volume":"2016","author":"M Chudnovsky","year":"2016","unstructured":"Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring graphs without induced paths on six vertices. Proc. SODA 2016, 1774\u20131783 (2016)","journal-title":"Proc. SODA"},{"issue":"1","key":"1905_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Seymour, P., Robertson, N., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"1905_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jctb.2009.10.001","volume":"100","author":"M Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Seymour, P., Robertson, N., Thomas, R.: \n                    \n                      \n                    \n                    $$K_4$$\n                    \n                      \n                        \n                          K\n                          4\n                        \n                      \n                    \n                  -free graphs with no odd holes. J. Combin. Theory Ser. B 100, 313\u2013331 (2010)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1905_CR12","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. I. Extending an excellent precoloring, \n                    arXiv:1802.02282v2\n                    \n                   [math.CO] (2018)"},{"key":"1905_CR13","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring \n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. II. Finding an excellent precoloring, \n                    arXiv:1802.02283v2\n                    \n                   [math.CO] (2018)"},{"key":"1905_CR14","unstructured":"Dabrowski, K. K., Dross, F., Paulusma, D.: Colouring diamond-free graphs. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Rasmus Pagh Ed., LIPICS, Article No. 16; pp. 16:1\u201316:14"},{"key":"1905_CR15","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1016\/j.disc.2012.12.019","volume":"313","author":"L Esperet","year":"2013","unstructured":"Esperet, L., Lemoine, L., Maffray, F., Morel, M.: The chromatic number of \n                    \n                      \n                    \n                    $$P_5, K_4$$\n                    \n                      \n                        \n                          \n                            P\n                            5\n                          \n                          ,\n                          \n                            K\n                            4\n                          \n                        \n                      \n                    \n                  -free graphs. Disc. Math. 313, 743\u2013754 (2013)","journal-title":"Disc. Math."},{"key":"1905_CR16","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1137\/120895834","volume":"28","author":"G Fan","year":"2014","unstructured":"Fan, G., Xu, B., Ye, T., Yu, X.: Forbidden subgraphs and \n                    \n                      \n                    \n                    $$3$$\n                    \n                      \n                        \n                          3\n                        \n                      \n                    \n                  -colorings. SIAM J. Disc. Math. 28, 1226\u20131256 (2014)","journal-title":"SIAM J. Disc. Math."},{"key":"1905_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory 84, 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"key":"1905_CR18","volume-title":"Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 2nd edn. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"1905_CR19","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. Disc. Math. 272, 285\u2013290 (2003)","journal-title":"Disc. Math."},{"key":"1905_CR20","doi-asserted-by":"publisher","first-page":"413","DOI":"10.4064\/am-19-3-4-413-441","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki Applicationes Mathematicae 19, 413\u2013441 (1987)","journal-title":"Zastosowania Matematyki Applicationes Mathematicae"},{"key":"1905_CR21","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.ejc.2015.06.005","volume":"51","author":"S Huang","year":"2016","unstructured":"Huang, S.: Improved complexity results on \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -coloring \n                    \n                      \n                    \n                    $$P_t$$\n                    \n                      \n                        \n                          P\n                          t\n                        \n                      \n                    \n                  -free graphs. Eur. J. Combin. 51, 336\u2013346 (2016)","journal-title":"Eur. J. Combin."},{"key":"1905_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., editors, Complexity of computer computations. Plenum, New York, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1905_CR23","unstructured":"Karthick, T.: Vertex coloring and cliques of certain \n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs and claw-free graphs. Ph.D. Thesis, IIT Madras (2010)"},{"key":"1905_CR24","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1007\/s00373-015-1651-1","volume":"32","author":"T Karthick","year":"2016","unstructured":"Karthick, T., Maffray, F.: Vizing bound for the chromatic number on some graph classes. Graphs Combin. 32, 1447\u20131460 (2016)","journal-title":"Graphs Combin."},{"key":"1905_CR25","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.jctb.2008.12.005","volume":"99","author":"T Kloks","year":"2009","unstructured":"Kloks, T., M\u00fcller, H., Vu\u0161kovi\u0107, K.: Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences. J. Combin. Theory. Ser. B 99, 733\u2013800 (2009)","journal-title":"J. Combin. Theory. Ser. B"},{"key":"1905_CR26","unstructured":"Kral, D., Kratochvil, J., Tuza, Z.S., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Proceedings of WG 2001, Lecture Notes in Computer Science 2204, 254\u2013262 (2001)"},{"key":"1905_CR27","first-page":"125","volume":"11","author":"R Mosca","year":"2009","unstructured":"Mosca, R.: Independent sets in (\n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  , diamond)-free graphs. Disc. Math. Theoret. Comput. Sci. 11, 125\u2013140 (2009)","journal-title":"Disc. Math. Theoret. Comput. Sci."},{"key":"1905_CR28","doi-asserted-by":"publisher","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. 3, 161\u2013162 (1955)","journal-title":"Colloq. Math."},{"key":"1905_CR29","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.disc.2012.10.019","volume":"313","author":"AV Pyatkin","year":"2013","unstructured":"Pyatkin, A.V.: Triangle-free \n                    \n                      \n                    \n                    $$2P_3$$\n                    \n                      \n                        \n                          2\n                          \n                            P\n                            3\n                          \n                        \n                      \n                    \n                  -free graphs are \n                    \n                      \n                    \n                    $$4$$\n                    \n                      \n                        \n                          4\n                        \n                      \n                    \n                  -colorable. Disc. Math. 313, 715\u2013720 (2013)","journal-title":"Disc. Math."},{"key":"1905_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: \n                    \n                      \n                    \n                    $$3$$\n                    \n                      \n                        \n                          3\n                        \n                      \n                    \n                  -colorability \n                    \n                      \n                    \n                    $$\\in \\cal{P}$$\n                    \n                      \n                        \n                          \u2208\n                          P\n                        \n                      \n                    \n                   for \n                    \n                      \n                    \n                    $$P_6$$\n                    \n                      \n                        \n                          P\n                          6\n                        \n                      \n                    \n                  -free graphs. Disc. Appl. Math. 136, 299\u2013313 (2004)","journal-title":"Disc. Appl. Math."},{"key":"1905_CR31","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. 20, 1\u201340 (2004)","journal-title":"Graphs Combin."},{"key":"1905_CR32","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0012-365X(01)00335-1","volume":"251","author":"B Randerath","year":"2002","unstructured":"Randerath, B., Schiermeyer, I., Tewes, M.: Three-colourability and forbidden subgraphs. II: polynomial algorithms. Disc. Math. 251, 137\u2013153 (2002)","journal-title":"Disc. Math."},{"key":"1905_CR33","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0095-8956(87)90048-7","volume":"42","author":"A Tucker","year":"1987","unstructured":"Tucker, A.: Coloring perfect \n                    \n                      \n                    \n                    $$(K_4 -e)$$\n                    \n                      \n                        \n                          (\n                          \n                            K\n                            4\n                          \n                          -\n                          e\n                          )\n                        \n                      \n                    \n                  -free graphs. J. Combin. Theory Ser. B 42, 313\u2013318 (1987)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1905_CR34","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs, New Jersey (2000)","edition":"2"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-018-1905-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-018-1905-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-018-1905-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T23:41:48Z","timestamp":1558050108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-018-1905-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,17]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1905"],"URL":"https:\/\/doi.org\/10.1007\/s00373-018-1905-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,17]]},"assertion":[{"value":"23 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}