Geodesic
Graph Classes Generated by Mycielskians
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1163-1173

Voir la notice de l'article provenant de la source Library of Science

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 of order 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.
Keywords: Mycielski graphs, graph coloring, chromatic number 
@article{DMGT_2020_40_4_a14,
     author = {Borowiecki, Mieczys law and Borowiecki, Piotr and Drgas-Burchardt, Ewa and Sidorowicz, El\.zbieta},
     title = {Graph {Classes} {Generated} by {Mycielskians}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1163--1173},
     publisher = {mathdoc},
     volume = {40},
     number = {4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a14/}
}
TY  - JOUR
AU  - Borowiecki, Mieczys law
AU  - Borowiecki, Piotr
AU  - Drgas-Burchardt, Ewa
AU  - Sidorowicz, Elżbieta
TI  - Graph Classes Generated by Mycielskians
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 1163
EP  - 1173
VL  - 40
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a14/
LA  - en
ID  - DMGT_2020_40_4_a14
ER  - 
%0 Journal Article
%A Borowiecki, Mieczys law
%A Borowiecki, Piotr
%A Drgas-Burchardt, Ewa
%A Sidorowicz, Elżbieta
%T Graph Classes Generated by Mycielskians
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 1163-1173
%V 40
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a14/
%G en
%F DMGT_2020_40_4_a14
Borowiecki, Mieczys law; Borowiecki, Piotr; Drgas-Burchardt, Ewa; Sidorowicz, Elżbieta. Graph Classes Generated by Mycielskians. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1163-1173. http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a14/