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/

[1] A.J. Berger, I. Broere, S.J.T. Moagi and P. Mihók, Meet- and join-irreducibility of additive hereditary properties of graphs, Discrete Math. 251 (2002) 11–18. doi:10.1016/S0012-365X(01)00323-5

[2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5–50. doi:10.7151/dmgt.1037

[3] P. Borowiecki, Computational aspects of greedy partitioning of graphs, J. Comb. Optim. 35 (2018) 641–665. doi:10.1007/s10878-017-0185-2

[4] B. Brešar, J. Ferme, S. Klavžar and D.F. Rall, A survey on packing colorings, Discuss. Math. Graph Theory 40 (2020) 923–970. doi:10.7151/dmgt.2320

[5] B. Brešar, S. Klavžar, D.F. Rall and K. Wash, Packing chromatic number versus chromatic and clique number, Aequationes Math. 92 (2018) 497–513. doi:10.1007/s00010-017-0520-9

[6] M. Caramia and P. Dell’Olmo, A lower bound on the chromatic number of Mycielski graphs, Discrete Math. 235 (2001) 79–86. doi:10.1016/S0012-365X(00)00261-2

[7] G.J. Chang, L. Huang and X. Zhu, Circular chromatic number of Mycielski’s graphs, Discrete Math. 205 (1999) 23–37. doi:10.1016/S0012-365X(99)00033-3

[8] M. Cropper, A. Gyárfás and J. Lehel, Hall ratio of the Mycielski graphs, Discrete Math. 306 (2006) 1988–1990. doi:10.1016/j.disc.2005.09.020

[9] R. Diestel, Graph Theory (Springer, Berlin, 1997).

[10] T. Došlić, Mycielskians and matchings, Discuss. Math. Graph Theory 25 (2005) 261–266. doi:10.7151/dmgt.1279

[11] D.C. Fisher, Fractional colorings with large denominators, J. Graph Theory 20 (1995) 403–409. doi:10.1002/jgt.3190200403

[12] D.C. Fisher, P.A. 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

[13] Y.S. Kwon, J. Lee and Z. Zhang, Edge-chromatic numbers of Mycielski graphs, Discrete Math. 312 (2012) 1222–1225. doi:10.1016/j.disc.2011.12.011

[14] 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

[15] W. Li, J. Wu, P.C.B. Lam and G. Gu, Several parameters of generalized Mycielskians, Discrete Appl. Math. 154 (2006) 1173–1182. doi:10.1016/j.dam.2005.11.001

[16] D.D.-F. Liu, Circular chromatic number for iterated Mycielski graphs, Discrete Math. 285 (2004) 335–340. doi:10.1016/j.disc.2004.01.020

[17] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161–162. doi:10.4064/cm-3-2-161-162

[18] H.P. Patil and R. Pandiya Raj, On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361–371. doi:10.7151/dmgt.1670

[19] G. Simons, C. Tardif and D. Wehlau, Generalised Mycielski graphs, signature systems, and bounds on chromatic number, J. Combin. Theory Ser. B 122 (2017) 776–793. doi:10.1016/j.jctb.2016.09.007

[20] D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001).