{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:25Z","timestamp":1759063645149},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A 2-edge-colored graph is a pair<jats:inline-formula><jats:alternatives><jats:tex-math>$$(G, \\sigma )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03c3<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>where<jats:italic>G<\/jats:italic>is a graph, and<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sigma :E(G)\\rightarrow \\{\\text {'}+\\text {'},\\text {'}-\\text {'}\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03c3<\/mml:mi><mml:mo>:<\/mml:mo><mml:mi>E<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>)<\/mml:mo><mml:mo>\u2192<\/mml:mo><mml:mo>{<\/mml:mo><mml:mtext>'<\/mml:mtext><mml:mo>+<\/mml:mo><mml:mtext>'<\/mml:mtext><mml:mo>,<\/mml:mo><mml:mtext>'<\/mml:mtext><mml:mo>-<\/mml:mo><mml:mtext>'<\/mml:mtext><mml:mo>}<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is a function which marks all edges with signs. A 2-edge-colored coloring of the 2-edge-colored graph<jats:inline-formula><jats:alternatives><jats:tex-math>$$(G, \\sigma )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03c3<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is a homomorphism into a 2-edge-colored graph<jats:inline-formula><jats:alternatives><jats:tex-math>$$(H, \\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>H<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03b4<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The 2-edge-colored chromatic number of the 2-edge-colored graph<jats:inline-formula><jats:alternatives><jats:tex-math>$$(G, \\sigma )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03c3<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the minimum order of<jats:italic>H<\/jats:italic>. In this paper we show that for every 2-dimensional grid<jats:inline-formula><jats:alternatives><jats:tex-math>$$(G, \\sigma )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03c3<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>there exists a homomorphism from<jats:inline-formula><jats:alternatives><jats:tex-math>$$(G, \\sigma )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mi>G<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>\u03c3<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>into the 2-edge-colored Paley graph<jats:inline-formula><jats:alternatives><jats:tex-math>$$SP_9$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>S<\/mml:mi><mml:msub><mml:mi>P<\/mml:mi><mml:mn>9<\/mml:mn><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Hence, the 2-edge-colored chromatic number of the 2-edge-colored grids is at most 9. This improves the upper bound on this number obtained recently by Bensmail. Additionally, we show that 2-edge-colored chromatic number of the 2-edge-colored grids with 3 columns is at most\u00a08.<\/jats:p>","DOI":"10.1007\/s00373-020-02155-y","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T08:02:41Z","timestamp":1583913761000},"page":"831-837","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["2-Edge-Colored Chromatic Number of Grids is at Most 9"],"prefix":"10.1007","volume":"36","author":[{"given":"Janusz","family":"Dybizba\u0144ski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"key":"2155_CR1","unstructured":"Bensmail, J.: On the signed chromatic number of grids (2016). hal-01349656"},{"issue":"3","key":"2155_CR2","first-page":"365","volume":"75","author":"J Bensmail","year":"2019","unstructured":"Bensmail, J.: On the 2-edge-coloured chromatic number of grids. Aust. J. Combin. 75(3), 365\u2013384 (2019)","journal-title":"Aust. J. Combin."},{"issue":"4","key":"2155_CR3","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s00373-017-1807-2","volume":"33","author":"J Bensmail","year":"2017","unstructured":"Bensmail, J., Duffy, C., Sen, S.: Analogues of cliques for (m, n)-colored mixed graphs. Graph. Combin. 33(4), 735\u2013750 (2017)","journal-title":"Graph. Combin."},{"issue":"4","key":"2155_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ipl.2011.10.019","volume":"112","author":"J Dybizba\u0144ski","year":"2012","unstructured":"Dybizba\u0144ski, J., Nenca, A.: Oriented chromatic number of grids is greater than 7. Inf. Process. Lett. 112(4), 113\u2013117 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"2155_CR5","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0020-0190(02)00405-2","volume":"85","author":"G Fertin","year":"2003","unstructured":"Fertin, G., Raspaud, A., Roychowdhury, A.: On the oriented chromatic number of grids. Inf. Process. Lett. 85(5), 261\u2013266 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"2155_CR6","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1016\/j.dam.2009.09.017","volume":"158","author":"A Montejano","year":"2010","unstructured":"Montejano, A., Ochem, P., Pinlou, A., Raspaud, A., Sopena, \u00c9.: Homomorphisms of 2-edge-colored graphs. Discr. Appl. Math. 158(12), 1365\u20131379 (2010)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"2155_CR7","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1002\/jgt.22059","volume":"85","author":"P Ochem","year":"2017","unstructured":"Ochem, P., Pinlou, A., Sen, S.: Homomorphisms of 2-edge-colored triangle-free planar graphs. J. Graph Theory 85(1), 258\u2013277 (2017)","journal-title":"J. Graph Theory"},{"key":"2155_CR8","doi-asserted-by":"crossref","first-page":"270","DOI":"10.5486\/PMD.1962.9.3-4.11","volume":"9","author":"H Sachs","year":"1962","unstructured":"Sachs, H.: \u00dcber selbstkomplement\u00e4re graphen. Publ. Math. Debrecen 9, 270\u2013288 (1962)","journal-title":"Publ. Math. Debrecen"},{"key":"2155_CR9","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1016\/j.disc.2015.03.018","volume":"339","author":"\u00c9 Sopena","year":"2016","unstructured":"Sopena, \u00c9.: Homomorphisms and colourings of oriented graphs: an updated survey. Discr. Math. 339, 1993\u20132005 (2016)","journal-title":"Discr. Math."},{"issue":"2","key":"2155_CR10","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2004.06.014","volume":"92","author":"A Szepietowski","year":"2004","unstructured":"Szepietowski, A., Targan, M.: A note on the oriented chromatic number of grids. Inf. Process. Lett. 92(2), 65\u201370 (2004)","journal-title":"Inf. Process. Lett."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02155-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-020-02155-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02155-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T12:57:42Z","timestamp":1695905862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-020-02155-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,11]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["2155"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02155-y","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,11]]},"assertion":[{"value":"1 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}