Grafi Mycielskega in njihov kromatični indeks - Božič, Aljaž (Matrika, 2014)
Mycielski graphs are a special family of graphs with several interesting properties. Any simple graph can be expanded and transformed into a Mycielski graph, which contains the initial graph as a subgraph. In this article, we focus on the edge coloring of Mycielski graphs and we prove that regarding the edge chromatic number, every Mycielski graph belongs to Class 1, except the Mycielski graph of complete graph ?$K_2$?. We also show that with the Mycielski's construction on an initial graph we obtain a Mycielski graph whose chromatic number is one greater than the chromatic number of the initial graph. And if the initial graph is triangle-free, its Mycielski graph is also triangle-free.
Keywords: barvanje grafov; kromatični indeks; teorija grafov