DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 261-266
DOI: 10.7151/dmgt.1279

MYCIELSKIANS AND MATCHINGS

Tomislav Doslić

Department of Informatics and Mathematics
Faculty of Agriculture, University of Zagreb
Svetosimunska c. 25, 10000 Zagreb, Croatia
e-mail: doslic@math.hr

Abstract

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.

Keywords: Mycielskian, factor-critical graph, perfect matching, perfect 2-matching.

2000 Mathematics Subject Classification: 05C70, 05C75.

References

[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.

Received 15 July 2003
Revised 23 July 2004