Redkejši grafi z velikim kromatičnim številomKocbek, Matija (Avtor) Škrekovski, Riste (Mentor) kromatično številografi brez trikotnikovožinaneodvisnostno številoRamseyeva teorijadiskretna geometrijagraf Mycielskegazamični grafiverjetnostna metodaV delu raziščemo nekaj klasičnih konstrukcij družin grafov brez trikotnikov s poljubno velikim kromatičnim številom, kot so Tuttova konstrukcija, konstrukcija Mycielskega in zamični grafi. Za vsako konstrukcijo izpostavimo njene posebnosti. Predstavimo eksplicitno konstrukcijo nove velike parametrizirane družine grafov brez trikotnikov, ki posploši tisto, ki so jo opisali Codenotti, Pudlák in Resta, in ki ima pri določenih parametrih neodvisnostno število reda O(n²ᐟ³) in kromatično število reda Ω(n¹ᐟ³), kjer je n število vozlišč, kar doseže najmanjšo znano konstruktivno mejo za neodvisnostno število in največjo znano konstruktivno mejo za kromatično število nekega grafa brez trikotnikov. Podamo Erdősev klasični dokaz z verjetnostno metodo, da obstajajo grafi s poljubno veliko ožino in hkrati poljubno velikim kromatičnim številom. Podamo tudi nedavno predstavljeno eksplicitno konstrukcijo takšnih grafov.20252025-09-05 08:15:13Delo diplomskega seminarja/zaključno seminarsko delo/naloga171996UDK: 519.17VisID: 152601COBISS_ID: 247858179sl