{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T14:36:45Z","timestamp":1768747005721,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T00:00:00Z","timestamp":1421366400000},"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":["Combinatorica"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s00493-014-3132-1","type":"journal-article","created":{"date-parts":[[2015,1,20]],"date-time":"2015-01-20T11:08:51Z","timestamp":1421752131000},"page":"395-415","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Sabidussi versus Hedetniemi for three variations of the chromatic number"],"prefix":"10.1007","volume":"36","author":[{"given":"Chris","family":"Godsil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David E.","family":"Roberson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"\u0160\u00e1mal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Severini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,16]]},"reference":[{"key":"3132_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"S. Arora and B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009."},{"key":"3132_CR2","doi-asserted-by":"crossref","first-page":"1378","DOI":"10.1093\/ietfec\/e89-a.5.1378","volume":"E89-A","author":"D. Avis","year":"2006","unstructured":"D. Avis, J. Hasegawa, Y. Kikuchi and Y. Sasaki: A quantum protocol to win the graph colouring game on all Hadamard graphs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E89-A (2006), 1378\u20131381.","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci"},{"key":"3132_CR3","doi-asserted-by":"crossref","first-page":"1874","DOI":"10.1103\/PhysRevLett.83.1874","volume":"83","author":"G. Brassard","year":"1999","unstructured":"G. Brassard, R. Cleve and A. Tapp: Cost of exactly simulating quantum entan-glement with classical communication, Phys. Rev. Lett. 83 (1999), 1874\u20131877.","journal-title":"Phys. Rev. Lett"},{"key":"3132_CR4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/276698.276713","volume-title":"Proceedings of the thirtieth annual ACM symposium on Theory of computing","author":"H. Buhrman","year":"1998","unstructured":"H. Buhrman, R. Cleve and A. Wigderson: Quantum vs. classical communication and computation, in: Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC \u203298, 63\u201368. ACM, 1998."},{"key":"3132_CR5","doi-asserted-by":"crossref","unstructured":"P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini and A. Winter: On the quantum chromatic number of a graph, Electr. J. Comb. 14 (2007).","DOI":"10.37236\/999"},{"key":"3132_CR6","first-page":"236","volume-title":"19th IEEE Annual Conference on Computational Complexity","author":"R. Cleve","year":"2004","unstructured":"R. Cleve, P. Hoyer, B. Toner and J. Watrous: Consequences and limits of nonlocal strategies, in: 19th IEEE Annual Conference on Computational Complexity, 236\u2013249, 2004."},{"key":"3132_CR7","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P. Frankl","year":"1987","unstructured":"P. Frankl and Vojt\u011bech R\u00f6odl: Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), 259\u2013286.","journal-title":"Trans. Amer. Math. Soc"},{"key":"3132_CR8","volume-title":"Asian Conference on Quantum Information Science (AQIS'11)","author":"J. Fukawa","year":"2011","unstructured":"J. Fukawa, H. Imai and F. Le Gall: Quantum coloring games via symmetric SAT games, in: Asian Conference on Quantum Information Science (AQIS'11), 2011."},{"key":"3132_CR9","doi-asserted-by":"crossref","unstructured":"V. Galliard and S. Wolf: Pseudo-telepathy, entanglement, and graph colorings, in: IEEE International Symposium on Information Theory, 101, 2002.","DOI":"10.1109\/ISIT.2002.1023373"},{"key":"3132_CR10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02579272","volume":"1","author":"C. Godsil","year":"1981","unstructured":"C. Godsil: Equiarboreal graphs, Combinatorica 1 (1981), 163\u2013167.","journal-title":"Combinatorica"},{"key":"3132_CR11","volume-title":"Interesting graphs and their colourings, Unpublished notes","author":"C. Godsil","year":"2003","unstructured":"C. Godsil: Interesting graphs and their colourings, Unpublished notes, 2003."},{"key":"3132_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C. Godsil","year":"2001","unstructured":"C. Godsil and G. Royle: Algebraic Graph Theory, Springer-Verlag, New York, 2001."},{"key":"3132_CR13","first-page":"107","volume-title":"Graph symmetry, vol. 497 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci","author":"G. Hahn","year":"1997","unstructured":"G. Hahn and C. Tardif: Graph homomorphisms: structure and symmetry, in: Graph symmetry, vol. 497 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 107\u2013166, Kluwer Acad. Publ., 1997."},{"key":"3132_CR14","volume-title":"Handbook of Product Graphs, Discrete Mathematics and its Applications (Boca Raton)","author":"R. Hammack","year":"2011","unstructured":"R. Hammack, W. Imrich and S. Klav\u017ezar: Handbook of Product Graphs, Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, second edition, 2011.","edition":"second"},{"key":"3132_CR15","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"P. Hell and J. Ne\u0161set\u0159ril: Graphs and Homomorphisms, Oxford University Press, 2004."},{"key":"3132_CR16","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"D. Karger, R. Motwani and M. Sudan: Approximate graph coloring by semidef-inite programming, J. ACM 45 (1998), 246\u2013265.","journal-title":"J. ACM"},{"key":"3132_CR17","doi-asserted-by":"crossref","unstructured":"D. E. Knuth: The sandwich theorem, Electr. J. Comb. 1 (1994).","DOI":"10.37236\/1193"},{"key":"3132_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz: On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1\u20137.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"3132_CR19","volume-title":"New separations in zero-error channel capacity through projective Kochen-Specker sets and quantum coloring, Advanced online publication","author":"L. Man\u010dcinska","year":"2013","unstructured":"L. Man\u010dcinska, G. Scarpa and S. Severini: New separations in zero-error channel capacity through projective Kochen-Specker sets and quantum coloring, Advanced online publication, 2013."},{"key":"3132_CR20","first-page":"134","volume":"3","author":"R. J. McEliece","year":"1978","unstructured":"R. J. McEliece, E. R. Rodemich and H. C. Rumsey, Jr: The Lov\u00e1sz bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978), 134\u2013152.","journal-title":"J. Combin. Inform. System Sci"},{"key":"3132_CR21","volume-title":"Quantum Computation and Quantum Information","author":"M. A. Nielsen","year":"2000","unstructured":"M. A. Nielsen and I. L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000."},{"key":"3132_CR22","volume-title":"Graph homomorphisms for quantum players","author":"D. Roberson","year":"2012","unstructured":"D. Roberson and L. Man\u010dcinska: Graph homomorphisms for quantum players, 2012."},{"key":"3132_CR23","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BF01304186","volume":"68","author":"G. Sabidussi","year":"1964","unstructured":"G. Sabidussi: Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426\u2013438.","journal-title":"Monatsh. Math"},{"key":"3132_CR24","doi-asserted-by":"crossref","first-page":"2524","DOI":"10.1109\/TIT.2011.2178018","volume":"58","author":"G. Scarpa","year":"2012","unstructured":"G. Scarpa and S. Severini: Kochen-Specker sets and the rank-1 quantum chromatic number, IEEE Trans. Inf. Theory 58 (2012), 2524\u20132529.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3132_CR25","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A. Schrijver","year":"1979","unstructured":"A. Schrijver: A comparison of the Delsarte and Lov\u00e1sz bounds, IEEE Trans. Inform. Theory 25 (1979), 425\u2013429.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"3132_CR26","doi-asserted-by":"crossref","first-page":"1168","DOI":"10.1016\/j.ejc.2011.03.004","volume":"32","author":"X. Zhu","year":"2011","unstructured":"X. Zhu: The fractional version of Hedetniemi's conjecture is true, European J. Combin. 32 (2011), 1168\u20131175.","journal-title":"European J. Combin"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3132-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-3132-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-3132-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T05:02:58Z","timestamp":1690866178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-3132-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,16]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["3132"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-3132-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,16]]}}}