{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T16:41:10Z","timestamp":1720716070970},"reference-count":25,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T00:00:00Z","timestamp":1685491200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["project HOSIGRA (ANR\u201017\u2010CE40\u20100022)"],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005270","name":"Fujian Provincial Department of Science and Technology","doi-asserted-by":"publisher","award":["(2020J01268)"],"id":[{"id":"10.13039\/501100005270","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871439"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["754362"],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2023,11]]},"abstract":"Abstract<\/jats:title>A homomorphism of a signed graph to is a mapping of vertices and edges of to (respectively) vertices and edges of such that adjacencies, incidences, and the signs of closed walks are preserved. We observe in this work that, for , the \u2010coloring problem of a given graph can be captured by homomorphism to from a signed bipartite graph that is built from . Here assigns a negative sign to the edges of a perfect matching and a positive sign to the rest. Motivated by these reformulations and in connection with results on 3\u2010colorings of planar graphs, such as Gr\u00f6tzsch's theorem, we prove that any signed graph with the maximum average degree strictly less than admits a homomorphism to . For , we show that the maximum average degree being strictly less than 3 would suffice for a signed graph to admit a homomorphism to . Both of these bounds are tight. We discuss applications of our work to signed planar graphs and its connection to the study of homomorphisms of 2\u2010edge\u2010colored graphs. Among a number of interesting questions that are left open, a notable one is a possible extension of Steinberg's conjecture for the class of signed bipartite planar graphs.<\/jats:p>","DOI":"10.1002\/jgt.22992","type":"journal-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T09:28:40Z","timestamp":1685525320000},"page":"611-644","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$"],"prefix":"10.1002","volume":"104","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-6882-6034","authenticated-orcid":false,"given":"Reza","family":"Naserasr","sequence":"first","affiliation":[{"name":"CNRS, IRIF Universit\u00e9 Paris Cit\u00e9 Paris France"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-6851-3214","authenticated-orcid":false,"given":"Riste","family":"\u0160krekovski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Physics University of Ljubljana Ljubljana Slovenia"},{"name":"Faculty of Information Studies Novo Mesto Slovenia"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4722-4880","authenticated-orcid":false,"given":"Zhouningxin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences and LPMC Nankai University Tianjin China"}]},{"given":"Rongxing","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Mathematics Zhejiang Normal University Jinhua China"},{"name":"School of Mathematical Sciences University of Science and Technology of China Hefei Anhui China"}]}],"member":"311","published-online":{"date-parts":[[2023,5,31]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112664"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113257"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.11.001"},{"key":"e_1_2_11_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00081-9"},{"key":"e_1_2_11_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.021"},{"key":"e_1_2_11_7_1","doi-asserted-by":"publisher","DOI":"10.37236\/8478"},{"key":"e_1_2_11_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.07.006"},{"key":"e_1_2_11_9_1","unstructured":"Z.Dvo\u0159\u00e1k A simplified discharging proof of Gr\u00f6tzsch theorem ArXiv 1311.7636 2013."},{"key":"e_1_2_11_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000809"},{"key":"e_1_2_11_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.06.005"},{"key":"e_1_2_11_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_11_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22742"},{"key":"e_1_2_11_14_1","article-title":"Circular (4\u2212\u03f5) $(4-\\epsilon )$\u2010coloring of some classes of signed graphs","author":"Kardo\u0161 F.","year":"2023","journal-title":"SIAM J. Discrete Math"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3020-x"},{"key":"e_1_2_11_16_1","doi-asserted-by":"publisher","DOI":"10.37236\/4938"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.37236\/9938"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.11.002"},{"key":"e_1_2_11_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21817"},{"key":"e_1_2_11_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1654-y"},{"key":"e_1_2_11_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103222"},{"key":"e_1_2_11_22_1","unstructured":"R.NaserasrandZ.Wang Signed bipartite circular cliques and a bipartite analogue of Gr\u00f6tzsch's theorem ArXiv 219.1261800 2021."},{"key":"e_1_2_11_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70391-1"},{"key":"e_1_2_11_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00029-7"},{"key":"e_1_2_11_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90144-3"},{"key":"e_1_2_11_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(82)90033-6"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,18]],"date-time":"2023-09-18T10:45:25Z","timestamp":1695033925000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,31]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.1002\/jgt.22992"],"URL":"http:\/\/dx.doi.org\/10.1002\/jgt.22992","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,31]]},"assertion":[{"value":"2020-12-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}