Proper Edge Colorings of Cartesian Products with Rainbow C4-s

Gyárfás, András and Sárközy, Gábor (2023) Proper Edge Colorings of Cartesian Products with Rainbow C4-s. GRAPHS AND COMBINATORICS, 39 (5). ISSN 0911-0119

Preview

Text s00373-023-02697-x.pdf - Published Version Download (1MB) | Preview

Abstract

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 a B-coloring if every 4-cycle of G is colored with four different colors. Let q B(G) denote the smallest number of colors needed for a B-coloring of G. Here we look at q B(G) for Cartesian products of paths and cycles. Our main result is that q B(G) is equal to the chromatic index of G for grids, i.e. for Cartesian products of paths (apart from a few exceptions). This extends an earlier result for the case when G is the d-dimensional cube. Our main tool is a lemma which gives q B(G◻H) ≤ qB(G) + qB(H) if

Actions (login required)

Edit Item