304 KB38 KB201420242014Božič, Aljažštevilka:1letnik:114 str.COBISSID_HOST:17127257ISSN:2385-8567URN:URN:NBN:SI:doc-4LHF3GCFslZaložba Fakultete za matematiko in fiziko Univerze v LjubljaniMatrikabarvanje grafovkromatični indeksteorija grafovGrafi Mycielskega in njihov kromatični indeks|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-freeGrafi 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 osredotočimo na barvanje povezav grafov Mycielskega in dokažemo, da glede na kromatični indeks vsi grafi iz te družine pripadajo razredu 1, razen graf Mycielskega polnega grafa ?$K_2$?. 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 vsebujeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of Slovenia