On the 2-edge-coloured chromatic number of grids

Julien Bensmail (1)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications

The oriented (resp. 2-edge-coloured) chromatic number χₒ(G) (resp. χ₂(G)) of an undirected graph G is defined as the maximum oriented (resp. 2-edge-coloured) chromatic number of an orientation (resp. signature) of G. Although the difference between χₒ(G) and χ₂(G) can be arbitrarily large, there are, however, contexts in which these two parameters are quite comparable. We here compare the behaviour of these two parameters in the context of (square) grids. While a series of works has been dedicated to the oriented chromatic number of grids, we are not aware of any work dedicated to their 2-edge-coloured chromatic number. We investigate this throughout this paper. We show that the maximum 2-edge-coloured chromatic number of a grid lies in between 8 and 11. We also focus on 2-row grids and 3-row grids, and exhibit bounds on their 2-edge-coloured chromatic number, some of which are tight. Although our results indicate that the oriented chromatic number and the 2-edge-coloured chromatic number of grids are close in general, they also show that these parameters may differ, even for easy instances.

Mots clés: grids; oriented chromatic number; 2-edge-coloured chromatic number

Domaines: Mathématique discrète [cs.DM]

Julien Bensmail. On the 2-edge-coloured chromatic number of grids. The Australasian Journal of Combinatorics, 2019, 75 (3), pp.365-384. ⟨hal-02264958v2⟩