0
$\begingroup$

Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.

Now, is there a way to choose disjoint matchings from the three bipartitie subgraphs such that the union of the three disjoint matchings yields us two disjoint maximal matchings of $G$. We could easily get one maximal matching by the union of three disjoint matchings obtained from the three distinct bipartite subgraphs, but getting two maximal matchings seems hard to me at present. Maybe, we must use some symmeteric difference of two matchings. But, anyways, it is unclear. Any hints? What if the graph $G$ were 1-factorizable, or, Class $1$? Thanks beforehand.

Improve this question
$\endgroup$
4
  • $\begingroup$ @GerryMyerson your comment was valid. Why did you delete the comment. Edited the question $\endgroup$
    – vidyarthi
    Commented Aug 26, 2019 at 13:13
  • $\begingroup$ I wasn't sure whether I was missing some distinction between maximal matchings and maximum matchings. I'm glad you found my comment helpful. $\endgroup$
    – Gerry Myerson
    Commented Aug 26, 2019 at 23:50
  • $\begingroup$ Does every 3-partite graph have several maximal matchings? $\endgroup$
    – M. Winter
    Commented Aug 27, 2019 at 13:27
  • $\begingroup$ @M.Winter ok, edited the question. Actually, if the maximum degree of the graph is $\ge3$, then I think it should have $\ge3$ maximal matchings, irrespective of regularity, albeit of different cardinality $\endgroup$
    – vidyarthi
    Commented Aug 27, 2019 at 13:56

1 Answer 1

Reset to default
0
$\begingroup$

Such a matching cannot be said to exist if the maximum degree of the bipartite graphs $A\cup B$, $B\cup C$ and $C\cup A$ are the same as that of the whole graph. This is because, if the individual bipartite graphs had $E_1, E_2, $ and $E_3$ edges respectively, then the number of edges in the graph $G$ would be $E_1+E_2+E_3=X$. Now, two maximal matchings of $G$ would have combined cardinality at least $\lfloor\frac{2X}{\Delta+1}\rfloor$. On the other hand the maximal matchings in the bipartite subgraphs together would have maximum cardinality at most $\lfloor\frac{E_1}{\Delta}\rfloor+\lfloor\frac{E_2}{\Delta}\rfloor+\lfloor\frac{E_3}{\Delta}\rfloor\le \lfloor\frac{2X}{\Delta}\rfloor\neq\lfloor\frac{X}{\Delta+1}\rfloor$ generally, as the bipartite graphs have chromatic index $\Delta$. Therefore the maximum degree of the bipartite graphs must be less than that of the original graph for existence of such a phenomenon

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .