{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T05:20:28Z","timestamp":1697174428826},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T00:00:00Z","timestamp":1691971200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T00:00:00Z","timestamp":1691971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ELKH Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2023,10]]},"abstract":"Abstract<\/jats:title>Related to the famous (7,4)-problem, in an earlier paper we introduced B-colorings. We call a proper edge coloring of a graph G<\/jats:italic> a B-coloring if every 4-cycle of G<\/jats:italic> is colored with four different colors. Let $$q_B(G)$$<\/jats:tex-math>\n \n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denote the smallest number of colors needed for a B-coloring of G<\/jats:italic>. Here we look at $$q_B(G)$$<\/jats:tex-math>\n \n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for Cartesian products of paths and cycles. Our main result is that $$q_B(G)$$<\/jats:tex-math>\n \n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is equal to the chromatic index of G<\/jats:italic> for grids, i.e. for Cartesian products of paths (apart from a few exceptions). This extends an earlier result for the case when G<\/jats:italic> is the d<\/jats:italic>-dimensional cube. Our main tool is a lemma which gives $$q_B(G\\square H)\\le q_B(G)+q_B(H)$$<\/jats:tex-math>\n \n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n \u25a1<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if $$\\chi (G)\\le q_B(H), \\chi (H)\\le q_B(G)$$<\/jats:tex-math>\n \n \u03c7<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n \u03c7<\/mml:mi>\n \n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2264<\/mml:mo>\n \n q<\/mml:mi>\n B<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\chi (G)$$<\/jats:tex-math>\n \n \u03c7<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the chromatic number of G<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00373-023-02697-x","type":"journal-article","created":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T10:03:13Z","timestamp":1692007393000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Proper Edge Colorings of Cartesian Products with Rainbow $$C_4$$-s"],"prefix":"10.1007","volume":"39","author":[{"given":"Andr\u00e1s","family":"Gy\u00e1rf\u00e1s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor N.","family":"S\u00e1rk\u00f6zy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,14]]},"reference":[{"key":"2697_CR1","unstructured":"Brown, W.G., Erd\u0151s, P., S\u00f3s, V.T.: Some extremal problems on $$r$$-graphs, In: New directions in the theory of graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, Academic Press, New York, pp. 55\u201363 (1973)"},{"key":"2697_CR2","first-page":"13","volume":"3","author":"K Deng","year":"2012","unstructured":"Deng, K., Liu, X.S., Tian, S.L.: Star edge coloring of $$d$$-dimensional grids. J. East China Norm. Univ. Sci. Ed. 3, 13\u201316 (2012)","journal-title":"J. East China Norm. Univ. Sci. Ed."},{"key":"2697_CR3","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.21644","volume":"72","author":"Z Dvo\u0159ak","year":"2013","unstructured":"Dvo\u0159ak, Z., Mohar, B., \u0160\u00e1mal, R.: Star chromatic index. J. Graph Theory 72, 313\u2013326 (2013)","journal-title":"J. Graph Theory"},{"key":"2697_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01195000","volume":"17","author":"P Erd\u0151s","year":"1997","unstructured":"Erd\u0151s, P., Gy\u00e1rf\u00e1s, A.: A variant of the classical Ramsey problem. Combinatorica 17, 459\u2013467 (1997)","journal-title":"Combinatorica"},{"key":"2697_CR5","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1002\/jgt.3190170507","volume":"17","author":"RJ Faudree","year":"1993","unstructured":"Faudree, R.J., Gy\u00e1rf\u00e1s, A., Lesniak, L., Schelp, R.H.: Rainbow coloring of the cube. J. Graph Theory 17, 607\u2013612 (1993)","journal-title":"J. Graph Theory"},{"key":"2697_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/(SICI)1097-0118(199611)23:3<297::AID-JGT9>3.0.CO;2-N","volume":"23","author":"RJ Faudree","year":"1996","unstructured":"Faudree, R.J., Gy\u00e1rf\u00e1s, A., Schelp, R.H.: An edge coloring problem for graph products. J. Graph Theory 23, 297\u2013302 (1996)","journal-title":"J. Graph Theory"},{"key":"2697_CR7","unstructured":"Gy\u00e1rf\u00e1s, A., S\u00e1rk\u00f6zy, G.N.: \u201cLess\u201d strong chromatic indices and the $$(7,4)$$-conjecture, to appear in Studia Sci. Math. Hung"},{"key":"2697_CR8","unstructured":"Lei, H., Shi, Y.: A survey on star edge-coloring of graphs, arXiv:2009.08017"},{"key":"2697_CR9","unstructured":"Omoomi, B., Dastjerdi, M.V.: Star edge coloring of the Cartesian product of graphs, arXiv:1802.01300"},{"key":"2697_CR10","doi-asserted-by":"publisher","first-page":"515","DOI":"10.4153\/CJM-1957-060-7","volume":"9","author":"G Sabidussi","year":"1957","unstructured":"Sabidussi, G.: Graphs with given group and given graph-theoretical properties. Can. J. Math. 9, 515\u2013525 (1957)","journal-title":"Can. J. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02697-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-023-02697-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02697-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T04:03:52Z","timestamp":1697083432000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-023-02697-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,14]]},"references-count":10,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["2697"],"URL":"https:\/\/doi.org\/10.1007\/s00373-023-02697-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,14]]},"assertion":[{"value":"3 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"98"}}