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 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 vsebuje.

Pravice

URN

URN:NBN:SI:DOC-4LHF3GCF

COBISSID

17127257

Objavljeno

13.02.2025

Metapodatki

Citiranje

APA:

Božič, Aljaž (2014). Grafi Mycielskega in njihov kromatični indeks. Matrika, letnik 1, številka 1, 14 str. URN:NBN:SI:DOC-4LHF3GCF from http://www.dlib.si

MLA:

Božič, Aljaž. "Grafi Mycielskega in njihov kromatični indeks." Matrika letnik 1. številka 1 (2014) 14 str..
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-4LHF3GCF>

Matrika
2014-
(Zbirni zapis)