Mycielskians and matchings

• Autorzy: Tomislav Doslić
• Języki publikacji: EN

Abstrakty

EN

It is shown in this note that some matching-related properties of graphs, such as their factor-criticality, regularizability and the existence of perfect 2-matchings, are preserved when iterating Mycielski's construction.

Słowa kluczowe

EN

Mycielskian; factor-critical graph; perfect matching; perfect 2-matching

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 3
• Strony: 261-266

Daty

wydano

2005

otrzymano

2003-07-15

poprawiono

2004-07-23

Twórcy

autor

Tomislav Doslić

• Department of Informatics and Mathematics, Faculty of Agriculture, University of Zagreb, Svetosimunska c. 25, 10000 Zagreb, Croatia

Bibliografia

• [1] D.C. Fisher, P. McKenna and E.D. Boyer, Hamiltonicity, diameter, domination, packing and biclique partitions of Mycielski's graphs, Discrete Appl. Math. 84 (1998) 93-105, doi: 10.1016/S0166-218X(97)00126-1.
• [2] M. Larsen, J. Propp and D. Ullman, The fractional chromatic number of Mycielski's graphs, J. Graph Theory 19 (1995) 411-416, doi: 10.1002/jgt.3190190313.
• [3] L. Lovász and M.D. Plummer, Matching Theory, Ann. Discr. Math. 29 (North-Holland, Amsterdam, The Netherlands, 1986).
• [4] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161-162.

Identyfikatory

DOI

10.7151/dmgt.1279