{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:53Z","timestamp":1740107153288,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"vor","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":[[2020,1]]},"DOI":"10.1007\/s00373-019-02123-1","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T15:56:39Z","timestamp":1576511799000},"page":"125-138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Intersection of Two Vertex Coloring Problems"],"prefix":"10.1007","volume":"36","author":[{"given":"Ang\u00e8le M.","family":"Foley","sequence":"first","affiliation":[]},{"given":"Dallas J.","family":"Fraser","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6782-1194","authenticated-orcid":false,"given":"Ch\u00ednh T.","family":"Ho\u00e0ng","sequence":"additional","affiliation":[]},{"given":"Kevin","family":"Holmes","sequence":"additional","affiliation":[]},{"given":"Tom P.","family":"LaMantia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,14]]},"reference":[{"key":"2123_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"},{"key":"2123_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. J. Combin. Theory 9, 129\u2013135 (1970)","journal-title":"J. Combin. Theory"},{"key":"2123_CR3","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114 (1961)"},{"volume-title":"Topics on Perfect Graphs","year":"1984","key":"2123_CR4","unstructured":"Berge, C., Chv\u00e1tal, V. (eds.): Topics on Perfect Graphs. North-Holland, Amsterdam (1984)"},{"key":"2123_CR5","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00224-004-1154-6","volume":"38","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.O., Mosca, R.: New graph classes of bounded clique-width. Theory Comput. Syst. 38, 623\u2013645 (2005)","journal-title":"Theory Comput. Syst."},{"key":"2123_CR6","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00224-005-1199-1","volume":"39","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Engelfriet, J., Le, H.O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theory Comput. Syst. 39, 561\u2013590 (2006)","journal-title":"Theory Comput. Syst."},{"key":"2123_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"2123_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"2123_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 25(1\u20132), 71 (1961)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"2123_CR10","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.dam.2016.08.016","volume":"231","author":"DJ Fraser","year":"2017","unstructured":"Fraser, D.J., Hamel, A.M., Ho\u00e0ng, C.T., Holmes, K., LaMantia, T.P.: Characterizations of ($$4K_1, C_4, C_5$$)-free graphs. Discrete Appl. Math. 231, 166\u2013174 (2017)","journal-title":"Discrete Appl. Math."},{"key":"2123_CR11","unstructured":"Gaspers, S., Huang, S., Paulusma, D.: Colouring square-free graphs without long induced paths. arXiv:1805.08270"},{"key":"2123_CR12","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"P Golovach","year":"2017","unstructured":"Golovach, P., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84, 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"key":"2123_CR13","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"2123_CR14","volume-title":"Topics on Perfect Graphs","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. North-Holland, Amsterdam (1984)"},{"key":"2123_CR15","unstructured":"Gurski, F.: Graph operations on clique-width bounded graphs. arXiv:cs\/0701185 (2007)"},{"key":"2123_CR16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253\u2013267 (1972)","journal-title":"Discrete Math."},{"key":"2123_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.dam.2015.02.015","volume":"216","author":"VV Lozin","year":"2017","unstructured":"Lozin, V.V., Malyshev, D.S.: Vertex colouring of graphs with few obstructions. Discrete Appl. Math. 216, 273\u2013284 (2017). https:\/\/doi.org\/10.1016\/j.dam.2015.02.015","journal-title":"Discrete Appl. Math."},{"key":"2123_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/S0895480102419755","volume":"18","author":"VV Lozin","year":"2004","unstructured":"Lozin, V.V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195\u2013206 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"2123_CR19","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/s10878-016-0008-x","volume":"33","author":"D Malyshev","year":"2017","unstructured":"Malyshev, D.: Polynomial-time approximation algorithms for the coloring problem in some cases. J. Combin. Optim. 33(3), 809\u2013813 (2017)","journal-title":"J. Combin. Optim."},{"key":"2123_CR20","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.03.043","volume":"377","author":"M Rao","year":"2007","unstructured":"Rao, M.: MSOL partitioning problems on graphs of bounded tree width and clique-width. Theor. Comput. Sci. 377, 260\u2013267 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"2123_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221\u2013232 (1985)","journal-title":"Discrete Math."},{"key":"2123_CR22","volume-title":"Topics on Perfect Graphs","author":"SH Whitesides","year":"1984","unstructured":"Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. North-Holland, Amsterdam (1984)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-019-02123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-019-02123-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-019-02123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:31:23Z","timestamp":1607819483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-019-02123-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,14]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["2123"],"URL":"https:\/\/doi.org\/10.1007\/s00373-019-02123-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2019,12,14]]},"assertion":[{"value":"28 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}