zbMATH — the first resource for mathematics

Defining sets in vertex colorings of graphs and latin rectangles. (English) Zbl 0879.05028
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\).

05C15 Coloring of graphs and hypergraphs
05B15 Orthogonal arrays, Latin squares, Room squares
Full Text: DOI
[1] Behzad, M.; Mahmoodian, E.S., On topological invariants of the product of graphs, Canad. math. bull., 12, 157-166, (1969) · Zbl 0177.52402
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Elsevier New York · Zbl 1134.05001
[3] Cooper, J.; Donovan, D.; Seberry, J., Latin squares and critical sets of minimal size, Austral. J. combin., 4, 113-120, (1991) · Zbl 0759.05017
[4] Cooper, J.; Donovan, D.; Seberry, J., Secret sharing schemes arising from Latin squares, Bull. inst. combin. appl., 12, 33-43, (1994) · Zbl 0835.05009
[5] Hall, M., Combinatorial theory, ()
[6] Mahmoodian, E.S., Some problems in graph colorings, (), 215-218
[7] Street, A.P., Defining sets for block designs: an update, (), 307-320 · Zbl 0837.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.