REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/3592
Tytuł: The Mycielskian of a Graph
Autorzy: Rudnicki, Piotr
Stewart, Lorna
Data wydania: 2011
Data dodania: 6-gru-2015
Wydawca: De Gruyter Open
Źródło: Formalized Mathematics, Volume 19, Issue 1, 2011, Pages 27-34
Abstrakt: Let ω(G) and χ(G) be the clique number and the chromatic number of a graph G. Mycielski [11] presented a construction that for any n creates a graph Mn which is triangle-free (ω(G) = 2) with χ(G) > n. The starting point is the complete graph of two vertices (K2). M(n+1) is obtained from Mn through the operation μ(G) called the Mycielskian of a graph G. We first define the operation μ(G) and then show that ω(μ(G)) = ω(G) and χ(μ(G)) = χ(G) + 1. This is done for arbitrary graph G, see also [10]. Then we define the sequence of graphs Mn each of exponential size in n and give their clique and chromatic numbers.
Afiliacja: Rudnicki Piotr - University of Alberta, Edmonton, Canada
Stewart Lorna - University of Alberta, Edmonton, Canada
URI: http://hdl.handle.net/11320/3592
DOI: 10.2478/v10037-011-0005-6
ISSN: 1426-2630
1898-9934
Typ Dokumentu: Article
Występuje w kolekcji(ach):Formalized Mathematics, 2011, Volume 19, Issue 1

Pliki w tej pozycji:
Plik Opis RozmiarFormat 
v10037-011-0005-6.pdf265,61 kBAdobe PDFOtwórz
Pokaż pełny widok rekordu Zobacz statystyki


Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL Creative Commons