{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:58Z","timestamp":1740109318474,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:00:00Z","timestamp":1669248000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:00:00Z","timestamp":1669248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Natural Sciences and Engineering Research Council of Canada, the Killam Trust"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Research Council","award":["725978"],"award-info":[{"award-number":["725978"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider two variants of <jats:italic>orthogonal colouring games<\/jats:italic> on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of <jats:inline-formula><jats:alternatives><jats:tex-math>$$m\\in {\\mathbb {N}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the <jats:italic>normal play variant<\/jats:italic>, the first player unable to move loses. In the <jats:italic>scoring variant<\/jats:italic>, each player aims to maximise their <jats:italic>score<\/jats:italic>, which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are <jats:sc>PSPACE<\/jats:sc>-complete. An involution <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sigma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c3<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph <jats:italic>G<\/jats:italic> is <jats:italic>strictly matched<\/jats:italic> if its fixed point set induces a clique and <jats:inline-formula><jats:alternatives><jats:tex-math>$$v\\sigma (v)\\in E(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mi>\u03c3<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any non-fixed point <jats:inline-formula><jats:alternatives><jats:tex-math>$$v\\in V(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Andres et al. (Theor Comput Sci 795:312\u2013325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.\n<\/jats:p>","DOI":"10.1007\/s00453-022-01069-w","type":"journal-article","created":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T13:05:36Z","timestamp":1669381536000},"page":"1067-1090","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Two Colouring Games"],"prefix":"10.1007","volume":"85","author":[{"given":"Stephan Dominique","family":"Andres","sequence":"first","affiliation":[]},{"given":"Fran\u00e7ois","family":"Dross","sequence":"additional","affiliation":[]},{"given":"Melissa A.","family":"Huggan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5634-9506","authenticated-orcid":false,"given":"Fionn","family":"Mc Inerney","sequence":"additional","affiliation":[]},{"given":"Richard J.","family":"Nowakowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,24]]},"reference":[{"issue":"9","key":"1069_CR1","doi-asserted-by":"publisher","first-page":"1980","DOI":"10.1016\/j.dam.2007.10.021","volume":"157","author":"SD Andres","year":"2009","unstructured":"Andres, S.D.: The incidence game chromatic number. Discrete Appl. Math. 157(9), 1980\u20131987 (2009)","journal-title":"Discrete Appl. Math."},{"key":"1069_CR2","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/j.tcs.2019.07.014","volume":"795","author":"SD Andres","year":"2019","unstructured":"Andres, S.D., Huggan, M., Mc Inerney, F., Nowakowski, R.: The orthogonal colouring game. Theor. Comput. Sci. 795, 312\u2013325 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"1069_CR3","unstructured":"Archdeacon, D., Dinitz, J., Harary, F.: Orthogonal edge colorings of graphs. In: Proceedings of the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, 1985), vol. 47, pp. 49\u201367 (1985)"},{"key":"1069_CR4","doi-asserted-by":"publisher","first-page":"2195","DOI":"10.1016\/j.disc.2013.05.019","volume":"313","author":"SC Ballif","year":"2013","unstructured":"Ballif, S.C.: Upper bounds on sets of orthogonal colorings of graphs. Discrete Math. 313, 2195\u20132205 (2013)","journal-title":"Discrete Math."},{"key":"1069_CR5","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1080\/00029890.2007.11920471","volume":"114","author":"T Bartnicki","year":"2007","unstructured":"Bartnicki, T., Grytczuk, J., Kierstead, H.A., Zhu, X.: The map-coloring game. Am. Math. Monthly 114, 793\u2013803 (2007)","journal-title":"Am. Math. Monthly"},{"key":"1069_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2013.02.032","volume":"485","author":"G Beaulieu","year":"2013","unstructured":"Beaulieu, G., Burke, K., Duch\u00eane, E.: Impartial coloring games. Theor. Comput. Sci. 485, 49\u201360 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"1069_CR7","doi-asserted-by":"publisher","first-page":"2533","DOI":"10.1007\/s00453-022-00973-5","volume":"84","author":"J Bensmail","year":"2022","unstructured":"Bensmail, J., Fioravantes, F., Mc Inerney, F., Nisse, N.: The largest connected subgraph game. Algorithmica 84(9), 2533\u20132555 (2022)","journal-title":"Algorithmica"},{"key":"1069_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2022.04.050","volume":"923","author":"J Bensmail","year":"2022","unstructured":"Bensmail, J., Mc Inerney, F.: On a vertex-capturing game. Theor. Comput. Sci. 923, 27\u201346 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1069_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1142\/S0129054191000091","volume":"2","author":"HL Bodlaender","year":"1991","unstructured":"Bodlaender, H.L.: On the complexity of some coloring games. Int. J. Found. Comput. Sci. 2, 133\u2013147 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1069_CR10","doi-asserted-by":"crossref","unstructured":"Caro, Y., Yuster R.: Orthogonal colorings of graphs. Electron. J. Combin. 6(1) (1999) Research paper 5","DOI":"10.37236\/1437"},{"key":"1069_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2020.03.022","volume":"824\u2013825","author":"ER Costa","year":"2020","unstructured":"Costa, E.R., Pessoa, V.L., Sampaio, R.M., Soares, R.: PSPACE-completeness of two graph coloring games. Theor. Comput. Sci. 824\u2013825, 36\u201345 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1069_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"RL Diestel","year":"2017","unstructured":"Diestel, R.L.: Graph Theory, 5th edn. Springer, Berlin (2017)","edition":"5"},{"key":"1069_CR13","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2021.05.028","volume":"878\u2013879","author":"\u00c9 Duch\u00eane","year":"2021","unstructured":"Duch\u00eane, \u00c9., Gonzalez, S., Parreau, A., R\u00e9mila, E., Solal, P.: INFLUENCE: a partizan scoring game on graphs. Theor. Comput. Sci. 878\u2013879, 26\u201346 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"1069_CR14","first-page":"143","volume":"35","author":"U Faigle","year":"1993","unstructured":"Faigle, U., Kern, W., Kierstead, H., Trotter, W.T.: On the game chromatic number of some classes of graphs. Ars Comb. 35, 143\u2013150 (1993)","journal-title":"Ars Comb."},{"key":"1069_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1038\/scientificamerican1081-23","volume":"244","author":"M Gardner","year":"1981","unstructured":"Gardner, M.: Mathematical games. Sci. Am. 244, 23\u201326 (1981)","journal-title":"Sci. Am."},{"issue":"1","key":"1069_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1002\/(SICI)1097-0118(199901)30:1<67::AID-JGT7>3.0.CO;2-M","volume":"30","author":"DJ Guan","year":"1999","unstructured":"Guan, D.J., Zhu, X.: Game chromatic number of outerplanar graphs. J. Graph Theory 30(1), 67\u201370 (1999)","journal-title":"J. Graph Theory"},{"key":"1069_CR17","first-page":"17","volume":"37","author":"PCB Lam","year":"1999","unstructured":"Lam, P.C.B., Shiu, W.C., Xu, B.: Edge game coloring of graphs. Graph Theory Notes N. Y. 37, 17\u201319 (1999)","journal-title":"Graph Theory Notes N. Y."},{"key":"1069_CR18","doi-asserted-by":"crossref","unstructured":"Larsson, U., Nowakowski, R.J., Neto, J.P., Santos, C.P.: Guaranteed scoring games. Electron. J. Combin. 23, Paper 3.27 (2016)","DOI":"10.37236\/5417"},{"key":"1069_CR19","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00182-017-0590-x","volume":"47","author":"U Larsson","year":"2018","unstructured":"Larsson, U., Nowakowski, R.J., Santos, C.P.: Games with guaranteed scores and waiting moves. Int. J. Game Theory 47, 653\u2013671 (2018)","journal-title":"Int. J. Game Theory"},{"issue":"4","key":"1069_CR20","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1017\/S0963548311000071","volume":"20","author":"P Micek","year":"2011","unstructured":"Micek, P., Walczak, B.: A graph-grabbing game. Comb. Probab. Comput. 20(4), 623\u2013629 (2011)","journal-title":"Comb. Probab. Comput."},{"key":"1069_CR21","series-title":"Annals of Mathematical Studies","first-page":"291","volume-title":"Contributions to the Theory of Games","author":"J Milnor","year":"1953","unstructured":"Milnor, J.: Sums of positional games. In: Contributions to the Theory of Games. Annals of Mathematical Studies, vol. 2, pp. 291\u2013301. Princeton University Press, Princeton (1953)"},{"key":"1069_CR22","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Boston (1993)"},{"key":"1069_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"1069_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16, 185\u2013225 (1978)","journal-title":"J. Comput. Syst. Sci."},{"issue":"15","key":"1069_CR25","doi-asserted-by":"publisher","first-page":"1526","DOI":"10.1016\/j.dam.2011.03.002","volume":"159","author":"A Shapovalov","year":"2011","unstructured":"Shapovalov, A.: Occupation games on graphs in which the second player takes almost all vertices. Discrete Appl. Math. 159(15), 1526\u20131527 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1069_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.ipl.2006.12.003","volume":"102","author":"E Sidorowicz","year":"2007","unstructured":"Sidorowicz, E.: The game chromatic number and the game colouring number of cactuses. Inf. Process. Lett. 102(4), 147\u2013151 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1069_CR27","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1006\/jctb.1998.1878","volume":"75","author":"X Zhu","year":"1999","unstructured":"Zhu, X.: The game coloring number of planar graphs. J. Comb. Theory Ser. B 75(2), 245\u2013258 (1999)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1069_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2007.04.004","volume":"98","author":"X Zhu","year":"2008","unstructured":"Zhu, X.: Refined activation strategy for the marking game. J. Comb. Theory Ser. B 98(1), 1\u201318 (2008)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01069-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01069-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01069-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T13:13:15Z","timestamp":1680095595000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01069-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,24]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1069"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01069-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,11,24]]},"assertion":[{"value":"2 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}