{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:48Z","timestamp":1740109308860,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the <jats:sc>Clique Coloring<\/jats:sc> problem which asks whether a given graph has a clique coloring with <jats:italic>q<\/jats:italic> colors. For fixed <jats:inline-formula><jats:alternatives><jats:tex-math>$$q \\ge 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>q<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we give an <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {O}^{\\star }(q^{{\\mathsf {tw}}})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>\u22c6<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>q<\/mml:mi>\n                        <mml:mi>tw<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm when the input graph is given together with one of its tree decompositions of width <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathsf {tw}} $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>tw<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) <jats:sc>Clique Coloring<\/jats:sc> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {XP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>XP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> parameterized by clique-width.<\/jats:p>","DOI":"10.1007\/s00453-021-00890-z","type":"journal-article","created":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T04:20:21Z","timestamp":1638159621000},"page":"273-303","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Structural Parameterizations of Clique Coloring"],"prefix":"10.1007","volume":"84","author":[{"given":"Lars","family":"Jaffke","sequence":"first","affiliation":[]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"issue":"1","key":"890_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0012-365X(91)90055-7","volume":"88","author":"T Andreae","year":"1991","unstructured":"Andreae, T., Schughart, M., Tuza, Z.: Clique-transversal sets of line graphs and complements of line graphs. Discrete Math. 88(1), 11\u201320 (1991)","journal-title":"Discrete Math."},{"issue":"3","key":"890_CR2","doi-asserted-by":"publisher","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., Sebo, A.: Coloring the maximal cliques of graphs. SIAM J. Discrete Math. 17(3), 361\u2013376 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"890_CR3","first-page":"15","volume":"11","author":"G Bacs\u00f3","year":"2009","unstructured":"Bacs\u00f3, G., Tuza, Z.: Clique-transversal sets and weak 2-colorings in graphs of small maximum degree. Discrete Math. Theor. Comput. Sci. 11(2), 15\u201324 (2009)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"890_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"890_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)"},{"key":"890_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.endm.2008.01.033","volume":"30","author":"CN Campos","year":"2008","unstructured":"Campos, C.N., Dantas, S., de Mello, C.P.: Colouring clique-hypergraphs of circulant graphs. Electron. Notes Discrete Math. 30, 189\u2013194 (2008)","journal-title":"Electron. Notes Discrete Math."},{"key":"890_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.endm.2009.11.047","volume":"35","author":"MR Cerioli","year":"2009","unstructured":"Cerioli, M.R., Korenchendler, A.L.: Clique-coloring circular-arc graphs. Electron. Notes Discrete Math. 35, 287\u2013292 (2009)","journal-title":"Electron. Notes Discrete Math."},{"key":"890_CR8","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.jctb.2015.09.008","volume":"116","author":"P Charbit","year":"2016","unstructured":"Charbit, P., Penev, I., Thomass\u00e9, S., Trotignon, N.: Perfect graphs of arbitrarily large clique-chromatic number. J. Combin. Theory Ser. B 116, 456\u2013464 (2016)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"890_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/jgt.22110","volume":"86","author":"M Chudnovsky","year":"2017","unstructured":"Chudnovsky, M., Lo, I.: Decomposing and clique-coloring (diamond, odd-hole)-free graphs. J. Graph Theory 86(1), 5\u201341 (2017)","journal-title":"J. Graph Theory"},{"key":"890_CR10","doi-asserted-by":"crossref","unstructured":"Cochefert, M., Kratsch, D.: Exact algorithms to clique-colour graphs. In: Geffert, V., Preneel, B., Rovan, B., Stuller, J., Tjoa, A.M. (eds.) Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), LNCS, vol. 8327, pp. 187\u2013198. Springer, New York (2014)","DOI":"10.1007\/978-3-319-04298-5_17"},{"issue":"2","key":"890_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"890_CR12","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(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"890_CR13","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Transactions on Algorithms 12(3), 41:1-41:24 (2016)","journal-title":"ACM Transactions on Algorithms"},{"key":"890_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"issue":"3","key":"890_CR15","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/jgt.20177","volume":"53","author":"D D\u00e9fossez","year":"2006","unstructured":"D\u00e9fossez, D.: Clique-coloring some classes of odd-hole-free graphs. J. Graph Theory 53(3), 233\u2013249 (2006)","journal-title":"J. Graph Theory"},{"key":"890_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, New York (2013)"},{"issue":"1","key":"890_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0097-3165(91)90009-6","volume":"57","author":"D Duffus","year":"1991","unstructured":"Duffus, D., Sands, B., Sauer, N., Woodrow, R.E.: Two-colouring all two-element maximal antichains. J. Combin. Theory Ser. A 57(1), 109\u2013116 (1991)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"5","key":"890_CR18","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"890_CR19","first-page":"9:1","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9:1-9:27 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"890_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"890_CR21","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"890_CR22","doi-asserted-by":"crossref","unstructured":"Jaffke, L., Jansen, B.M.P.: Fine-grained parameterized complexity analysis of graph coloring problems. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS, vol. 10236, pp. 345\u2013356. Springer (2017)","DOI":"10.1007\/978-3-319-57586-5_29"},{"key":"890_CR23","unstructured":"Jaffke, L., Lima, P.T., Lokshtanov, D.: b-Coloring parameterized by clique-width. In: Bl\u00e4ser, M., Monmege, B. (eds.) Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), LIPIcs, vol. 187, pp. 43:1\u201343:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021)"},{"key":"890_CR24","unstructured":"Jaffke, L., Lima, P.T., Philip, G.: Structural parameterizations of clique coloring. In: Esparza, J., Kr\u00e1l\u2019, D. (eds.) Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs, vol. 170, pp. 49:1\u201349:15. Schloss Dagstuhl (2020)"},{"key":"890_CR25","doi-asserted-by":"crossref","unstructured":"Klein, S., Morgana, A.: On clique-colouring of graphs with few $$P_4$$\u2019s. J. Braz. Comput. Soc. 18(2), 113\u2013119 (2012)","DOI":"10.1007\/s13173-011-0053-3"},{"key":"890_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and approximations, LNCS","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and approximations, LNCS, vol. 842. Springer, New York (1994)"},{"issue":"1","key":"890_CR27","doi-asserted-by":"publisher","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"},{"issue":"2","key":"890_CR28","first-page":"13:1","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13:1-13:30 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"890_CR29","volume-title":"Combinatorial Problems and Exercises","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises. North-Holland Publishing Co., London (1993)"},{"issue":"29","key":"890_CR30","doi-asserted-by":"publisher","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. Theoret. Comput. Sci. 412(29), 3487\u20133500 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"890_CR31","doi-asserted-by":"publisher","first-page":"128","DOI":"10.37236\/1458","volume":"6","author":"B Mohar","year":"1999","unstructured":"Mohar, B., \u0160krekovski, R.: The Gr\u00f6tzsch theorem for the hypergraph of maximal cliques. Electron. J. Combin. 6(1), 128 (1999)","journal-title":"Electron. J. Combin."},{"issue":"3","key":"890_CR32","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1002\/jgt.21870","volume":"81","author":"I Penev","year":"2016","unstructured":"Penev, I.: Perfect graphs with no balanced skew-partition are 2-clique-colorable. J. Graph Theory 81(3), 213\u2013235 (2016)","journal-title":"J. Graph Theory"},{"key":"890_CR33","unstructured":"Rao, M.: D\u00e9compositions de graphes et algorithmes efficaces. Ph.D. thesis, University of Metz (2006)"},{"issue":"24","key":"890_CR34","doi-asserted-by":"publisher","first-page":"6157","DOI":"10.1016\/j.disc.2007.11.039","volume":"308","author":"M Rao","year":"2008","unstructured":"Rao, M.: Clique-width of graphs defined by one-vertex extensions. Discrete Math. 308(24), 6157\u20136165 (2008)","journal-title":"Discrete Math."},{"key":"890_CR35","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/j.ejc.2013.08.003","volume":"36","author":"E Shan","year":"2014","unstructured":"Shan, E., Liang, Z., Kang, L.: Clique-transversal sets and clique-coloring in planar graphs. Eur. J. Comb. 36, 367\u2013376 (2014)","journal-title":"Eur. J. Comb."},{"key":"890_CR36","unstructured":"Vassilevska, W.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: Husfeldt, T., Kanj, I.A. (eds.) Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs, vol. 43, pp. 17\u201329. Schloss Dagstuhl, New York (2015)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00890-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00890-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00890-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T07:04:33Z","timestamp":1644908673000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00890-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["890"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00890-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"25 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}