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.

$\endgroup$
  • $\begingroup$ @GerryMyerson your comment was valid. Why did you delete the comment. Edited the question $\endgroup$ – vidyarthi Aug 26 '19 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 Aug 26 '19 at 23:50
  • $\begingroup$ Does every 3-partite graph have several maximal matchings? $\endgroup$ – M. Winter Aug 27 '19 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 Aug 27 '19 at 13:56
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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.