Maximum transversal in partial Latin squares and rainbow matchings
type: Item
instance of: scholarly article
title: Maximum transversal in partial Latin squares and rainbow matchings
zbMATH Open document ID: 1161.05017
author: Manouchehr Zaker
published in: Discrete Applied Mathematics
publication date: 2007-03-08T00:00:00Z
review text: A \(k\)-plex is a partial Latin square of order \(n\) containing \(kn\) entries such that exactly \(k\) entries lie in each row and column and each of \(n\) symbols occurs exactly \(k\) times [\textit{I. M. Wanless}, ''A generalization of transversals for Latin squares,'' Electron. J. Comb. 9, No.1, Research paper R12, 15 p. (2002); printed version J. Comb. 9, No.1 (2002; Zbl 0993.05033)]. A duplex is a \(k\)-plex with \(k=2\). The main theorem of the paper shows that the problem of determining whether there is a transversal of size \(k\) in a duplex is an \(\mathcal{NP}\)-complete problem (Theorem 2). Proof is based on the lemma : The MAX-IS problem is \(\mathcal{NP}\)-complete for any subgraph \(G\) of a graph \(H\) where, in \(H\), all vertices are of degree 3 and in \(G\), the number of vertices of degree one and two are each even numbers and all vertices of \(G\) except those of degree one can be covered by cycles of length even. (The MAX-IS problem is to determine whether there is an independent set of vertices of a given cardinality in a graph) The idea of \textbf{rainbow matching} is introduced. For each edge in a graph, assign a subset (= color set) from the set of colors \(\{1, 2, 3,\dots,k\}\). A rainbow matching is a set of distinct edges whose color sets have a system of distinct representatives (SDR). The size of a rainbow matching is the cardinality of the set of distinct edges. Theorem 4 restates Theorem 2 in terms of rainbow matching. It is also shown that a special case of the rainbow matching problem has a polynomial time solution. Open questions on independent paths, maximum size of a transversal in \(k\)-plexes and perfect rainbow matching are mentioned.
reviewed by: V. S. Ramamurthi
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5131582
zbMATH Keywords: Latin squares
zbMATH Keywords: independent sets
zbMATH Keywords: \(\mathcal{NP}\)-complete
zbMATH Keywords: rainbow matchings
MaRDI profile type: Publication
full work available at URL: j.dam.2006.08.002
OpenAlex ID: W2021366112
cites work: Combinatorial matrix theory
cites work: Coloured matchings in bipartite graphs
cites work: Q4873725
cites work: Introduction to algorithms
cites work: Q4769064
cites work: Q4198056
cites work: Transversals of latin squares and their generalizations
cites work: A generalization of transversals for Latin squares
cites work: Q4222172
DOI: 10.1016/J.DAM.2006.08.002
description: scientific article; zbMATH DE number 5131582