Izbrane teme sodobne fizike in matematike
Grafi Mycielskega so posebna družina grafov, za katero velja več zanimivih lastnosti. Poljuben enostaven graf lahko razširimo tako, da iz njega konstruiramo graf Mycielskega, ki začetni graf vsebuje kot podgraf. V članku se bomo osredotočili na barvanje povezav grafov Mycielskega in bomo dokazali, da glede na kromatični indeks vsi grafi iz te družine pripadajo razredu 1, razen graf Mycielskega polnega grafa K2. Pokazali bomo tudi, da s konstrukcijo Mycielskega iz nekega začetnega grafa dobimo graf, ki ima kromatično število za ena večje kot začetni graf, in če začetni graf ne vsebuje nobenih trikotnikov, jih tudi graf Mycielskega ne vsebuje.
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 will focus on the edge coloring of Mycielski graphs and we will prove that regarding the edge chromatic number, every Mycielski graph belongs to Class 1, except the Mycielski graph of complete graph K2. We will 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.