{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:06:52Z","timestamp":1761808012630},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T00:00:00Z","timestamp":1451865600000},"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":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0106-7","type":"journal-article","created":{"date-parts":[[2016,1,4]],"date-time":"2016-01-04T16:17:06Z","timestamp":1451924226000},"page":"786-814","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs"],"prefix":"10.1007","volume":"77","author":[{"given":"H. B. Mac\u00eado","family":"Filho","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. C. S.","family":"Machado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. M. H.","family":"de Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"issue":"3","key":"106_CR1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1137\/S0895480199359995","volume":"17","author":"G Bacs\u00f3","year":"2004","unstructured":"Bacs\u00f3, G., Gravier, S., Gy\u00e1rf\u00e1s, A., Preissmann, M., Seb\u0151, A.: Coloring the maximal cliques of graphs. SIAM J. Discrete Math. 17(3), 361\u2013376 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"106_CR2","doi-asserted-by":"crossref","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(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"106_CR3","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Lo, I.: Decomposing and clique-colouring diamond, odd-hole)-free graphs, manuscript 2015","DOI":"10.1002\/jgt.22110"},{"issue":"2","key":"106_CR4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.20387","volume":"62","author":"D D\u00e9fossez","year":"2009","unstructured":"D\u00e9fossez, D.: Complexity of clique-coloring odd-hole-free graphs. J. Graph Theory 62(2), 139\u2013156 (2009)","journal-title":"J. Graph Theory"},{"issue":"1\u20133","key":"106_CR5","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2005.01.014","volume":"337","author":"VMF Dias","year":"2005","unstructured":"Dias, V.M.F., de Figueiredo, C.M.H., Szwarcfiter, J.L.: Generating bicliques of a graph in lexicographic order. Theor. Comput. Sci. 337(1\u20133), 240\u2013248 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"14","key":"106_CR6","doi-asserted-by":"crossref","first-page":"1826","DOI":"10.1016\/j.dam.2007.03.017","volume":"155","author":"VMF Dias","year":"2007","unstructured":"Dias, V.M.F., de Figueiredo, C.M.H., Szwarcfiter, J.L.: On the generation of bicliques of a graph. Discrete Appl. Math. 155(14), 1826\u20131832 (2007)","journal-title":"Discrete Appl. Math."},{"key":"106_CR7","doi-asserted-by":"crossref","unstructured":"Filho, H.B.M., Machado, R.C.S., Figueiredo, C.M.H.: Clique-colouring and biclique-colouring unichord-free graphs. In: Proceedings of the Latin American International Conference on Theoretical Informatics, Lecture Notes in Computer Science, vol. 7256, pp. 530\u2013541. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29344-3_45"},{"key":"106_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco (1979)"},{"issue":"3\u20134","key":"106_CR9","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00453-010-9474-1","volume":"62","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. Algorithmica 62(3\u20134), 637\u2013658 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"106_CR10","doi-asserted-by":"crossref","first-page":"347","DOI":"10.7155\/jgaa.00326","volume":"18","author":"M Groshaus","year":"2014","unstructured":"Groshaus, M., Soulignac, F.J., Terlisky, P.: Star and biclique coloring and choosability. J. Graph Algorithms Appl. 18(3), 347\u2013383 (2014)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"106_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.20442","volume":"63","author":"M Groshaus","year":"2010","unstructured":"Groshaus, M., Szwarcfiter, J.L.: Biclique graphs and biclique matrices. J. Graph Theory 63(1), 1\u201316 (2010)","journal-title":"J. Graph Theory"},{"key":"106_CR12","volume-title":"The Petersen Graph","author":"DA Holton","year":"1973","unstructured":"Holton, D.A.: The Petersen Graph. Cambridge Univertsity Press, Cambridge (1973)"},{"issue":"4","key":"106_CR13","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"106_CR14","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"DS Johnson","year":"1985","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 6(3), 434\u2013451 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"106_CR15","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0196-6774(02)00221-3","volume":"45","author":"J Kratochv\u00edl","year":"2002","unstructured":"Kratochv\u00edl, J., Tuza, Z.: On the complexity of bicoloring clique hypergraphs of graphs. J. Algorithms 45(1), 40\u201354 (2002)","journal-title":"J. Algorithms"},{"key":"106_CR16","doi-asserted-by":"crossref","unstructured":"Machado, R.C.S., de Figueiredo, C.M.H.: Total chromatic number of square, unichord-free graphs. In: Proceedings of the International Symposium on Combinatorial Optimization (ISCO), Electronics Notes in Discrete Mathematics, vol. 36, pp. 671\u2013678 (2010)","DOI":"10.1016\/j.endm.2010.05.085"},{"issue":"16","key":"106_CR17","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1016\/j.dam.2011.03.024","volume":"159","author":"RCS Machado","year":"2011","unstructured":"Machado, R.C.S., de Figueiredo, C.M.H.: Total chromatic number of unichord-free graphs. Discrete Appl. Math. 159(16), 1851\u20131864 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"7\u20139","key":"106_CR18","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1016\/j.tcs.2009.12.018","volume":"411","author":"RCS Machado","year":"2010","unstructured":"Machado, R.C.S., de Figueiredo, C.M.H., Vu\u0161kovi\u0107, K.: Chromatic index of graphs with no cycle with a unique chord. Theor. Comput. Sci. 411(7\u20139), 1221\u20131234 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"106_CR19","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F Maffray","year":"1996","unstructured":"Maffray, F., Preissmann, M.: On the NP-completeness of the $$k$$ k -colorability problem for triangle-free graphs. Discrete Math. 162(1\u20133), 313\u2013317 (1996)","journal-title":"Discrete Math."},{"issue":"29","key":"106_CR20","doi-asserted-by":"crossref","first-page":"3487","DOI":"10.1016\/j.tcs.2011.02.038","volume":"412","author":"D Marx","year":"2011","unstructured":"Marx, D.: Complexity of clique coloring and related problems. Theor. Comput. Sci. 412(29), 3487\u20133500 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"106_CR21","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0012-365X(92)00058-Y","volume":"124","author":"CJH McDiarmid","year":"1994","unstructured":"McDiarmid, C.J.H., S\u00e1nchez-Arroyo, A.: Total colouring regular bipartite graphs is NP-hard. Discrete Math. 124(1\u20133), 155\u2013162 (1994)","journal-title":"Discrete Math."},{"issue":"5\u20136","key":"106_CR22","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0020-0190(99)00108-8","volume":"71","author":"L Nourine","year":"1999","unstructured":"Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inform. Process. Lett. 71(5\u20136), 199\u2013204 (1999)","journal-title":"Inform. Process. Lett."},{"issue":"2\u20133","key":"106_CR23","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1080\/09528130210164152","volume":"14","author":"L Nourine","year":"2002","unstructured":"Nourine, L., Raynaud, O.: A fast incremental algorithm for building lattices. J. Exp. Theor. Artif. Intell. 14(2\u20133), 217\u2013227 (2002)","journal-title":"J. Exp. Theor. Artif. Intell."},{"issue":"1","key":"106_CR24","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s004930070035","volume":"20","author":"E Prisner","year":"2000","unstructured":"Prisner, E.: Bicliques in graphs. I. Bounds on their number. Combinatorica 20(1), 109\u2013117 (2000)","journal-title":"Combinatorica"},{"issue":"2","key":"106_CR25","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"106_CR26","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/jgt.20405","volume":"63","author":"N Trotignon","year":"2010","unstructured":"Trotignon, N., Vu\u0161kovi\u0107, K.: A structure theorem for graphs with no cycle with a unique chord and its consequences. J. Graph Theory 63(1), 31\u201367 (2010)","journal-title":"J. Graph Theory"},{"key":"106_CR27","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, CA, 1978), pp. 253\u2013264. ACM, New York (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0106-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0106-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0106-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0106-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T04:53:37Z","timestamp":1567486417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0106-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,4]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["106"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0106-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,4]]}}}