20.500.12556/RUL-171996 Redkejši grafi z velikim kromatičnim številom delo diplomskega seminarja Sparse graphs with high chromatic number V 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. We explore several classical constructions of triangle-free graphs with arbitrarily large chromatic number, including those due to Tutte, Mycielski, and the family of shift graphs. For each construction, we highlight key structural properties and distinguishing features. Building on previous work by Codenotti, Pudlák, and Resta, we introduce an explicit construction of a new, parametrized family of triangle-free graphs that generalizes their construction. For certain parameter choices, this family achieves an independence number of order O(n²ᐟ³) and a chromatic number of order Ω(n¹ᐟ³) where n is the number of vertices, matching the best-known constructive bounds for triangle-free graphs. In addition, we revisit Erdős’s classical use of the probabilistic method to prove the existence of graphs with arbitrarily high girth and chromatic number, and we present a recent explicit construction achieving the same properties. kromatično število grafi brez trikotnikov ožina neodvisnostno število Ramseyeva teorija diskretna geometrija graf Mycielskega zamični grafi verjetnostna metoda chromatic number triangle-free graphs girth independence number Ramsey theory discrete geometry Mycielskian shift graphs probabilistic method true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-05 08:15:13 2025-09-05 08:15:16 2025-09-30 03:39:32 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 152601 247858179 18856.pdf 18856.pdf 1 E015093FC6369CDFC7BC88940B3915D1 67eed1b4f9fd80c8b6f13bbfe14fe1f7f4f53ec85cf59c374dc3bda337474204 8a71b441-8a1f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=215714 Fakulteta za matematiko in fiziko 0 0 0