Graph classes generated by Mycielskians

Mieczysław Borowiecki; Piotr Borowiecki; Ewa Drgas-Burchardt; Elżbieta Sidorowicz

doi:10.7151/dmgt.2345

Graph classes generated by Mycielskians

Abstract

In this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the chromatic number of the subgraph induced by all vertices that belong to at least one triangle is at most p. We also address the problem of characterizing the latter class in terms of forbidden graphs.

Citations

1

CrossRef
0

Web of Science
2

Scopus

Authors (4)

Cite as

Full text

download paper

downloaded 181 times

Publication version: Accepted or Published Version
License: open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: Discussiones Mathematicae Graph Theory no. 40, pages 1163 - 1173,
ISSN: 1234-3099
Language:: English
Publication year:: 2020
Bibliographic description:: Borowiecki M., Borowiecki P., Drgas-Burchardt E., Sidorowicz E.: Graph classes generated by Mycielskians// Discussiones Mathematicae Graph Theory -Vol. 40,iss. 4 (2020), s.1163-1173
DOI:: Digital Object Identifier (open in new tab) 10.7151/dmgt.2345
Verified by:: Gdańsk University of Technology