Graph classes generated by Mycielskians - Publication - Bridge of Knowledge

Search

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

  • 0

    CrossRef

  • 0

    Web of Science

  • 1

    Scopus

Authors (4)

Cite as

Full text

download paper
downloaded 134 times
Publication version
Accepted or Published Version
License
Creative Commons: CC-BY-NC-ND 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

seen 124 times

Recommended for you

Meta Tags