• 3
  • 3
  • 82
  • 82
IPM
30
YEARS OLD

“School of Mathematics”

Paper   IPM / M / 8417
   School of Mathematics
  Title: Maximum transversal in partial Latin squares and rainbow matchings
  Author(s): M. Zaker
  Status: Published
  Journal: Discrete Appl. Math.
  Vol.: 155
  Year: 2007
  Pages: 558-565
  Supported by: IPM
  Abstract:
In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an ,NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⎣n /2⎦− t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α( G) \geqslant nt, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right