“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 8417 |
|
| 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 n − t,
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 | |
