Defining sets in vertex colorings of graphs and latin rectangles (Q1356483): Difference between revisions

A set \(S\) of vertices of a graph \(G\) is called a defining set of vertex colourings of \(G\) if there exists a proper colouring \(\varphi\) of \(S\) using \(k\leq \chi(G)\) colours such that \(\varphi\) has a unique extension to a \(\chi (G)\)-colouring of \(G\). The cardinality of a minimum defining set of \(G\) is denoted by \(d_v (G)\). A critical set in an \(m \times n\) array, \(m\leq n\), is a set \(S\) of cells which are preoccupied with \(k\leq n\) symbols such that there is a unique extension of \(S\) to a latin rectangle of size \(m\times n\). Some lower bounds for \(d_v (G)\) are obtained and used to show that \[ \begin{aligned} d_v & (K_2 \times C_{2n+1}) = n+1; \\ d_v & (C_m \times K_n)= m(n-3) \text{ for }n \geq 6; \\ d_v & (P_m \times K_n) =m(n-3) +2 \text{ for } n\geq 6; \text{ and} \\ d_v & (K_m \times K_n) =m(n-m) \text{ if }n \geq m^2, \end{aligned} \] where \(P_m \times K_n\) is the Cartesian product of \(K_2\) and \(C_{2n+1}\). The authors also determine the size of smallest critical sets of a back circulant latin rectangle of size \(m\times n\), with \(2m\leq n\). It is conjectured that for any latin square of order \(n\), the size of a critical set is at least \(\lfloor {n^2 \over 4} \rfloor\). Reviewer's remark: Thayer Morrill and Dan Pritikin have studied defining sets and list-defining sets \(S\) in graphs in a slightly broader sense that a proper \(k\)-colouring \(\varphi\) of \(S\) has a unique extension to a proper \(k\)-colouring of \(G\), where \(\Delta (G)\leq k\leq \Delta (G)+1\).