- Tytuł:
- Graph Classes Generated by Mycielskians
- Autorzy:
-
Borowiecki, Mieczys law
Borowiecki, Piotr
Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta - Powiązania:
- https://bibliotekanauki.pl/articles/31348089.pdf
- Data publikacji:
- 2020-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Mycielski graphs
graph coloring
chromatic number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 1163-1173
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł