20.500.12556/DKUM-36848 IZREKI NORDHAUS-GADDUMOVEGA TIPA ZA NEKATERE KROMATIČNE INVARIANTE NORDHAUS-GADDUM TYPE THEOREMS FOR SOME CHROMATIC INVARIANTS Diplomska naloga obravnava izreke Nordhaus-Gaddumovega tipa za nekatere kromatične invariante. Na začetku predstavimo osnovne pojme teorije grafov, ki so potrebni za razumeva- nje nadaljne snovi. V nalogo so vključene nekatere kromatične invariante, kot so kromatično število, seznamsko kromatično število ter akromatično in psevdoakromatično število. Konec pa vključuje število mavrične povezanosti. Za vsoto in produkt kromatičnega števila grafa in njegovega komplementa določimo spodnjo in zgornjo mejo, prav tako določimo zgornjo mejo za vsoto seznamskega kromatičnega števila grafa in njegovega komplementa. Preverimo neenakosti, ki veljajo za akromatično in psevdoakromatično število in nazadnje določimo spodnjo in zgornjo mejo za vsoto števil mavrične povezanosti grafa in njegovega komplementa. This thesis focuses on the Nordhaus-Gaddum-type theorems for some chromatic invariants. We start by presenting the basic concepts of graph theory needed to understand the thesis. The task includes some chromatic invariants, such as the chromatic number, the list-chromatic number, the achromatic and the pseudoachromatic number. Furthermore, we study rainbow connection number. For sum and product of the chromatic number of a graph and its complement we introduce a lower and an upper bound. Likewise we introduce an upper bound for the sum of the list-chromatic number of a graph and its complement. We examine inequalities for the achromatic and the pseudoachromatic number and in the end introduce a lower and an upper bound for the sum of the rainbow connection number for a graph and its complement. kromatično število akromatično število psevdoakromatično število seznamsko kromatično število število mavrične povezanosti chromatic number achromatic number pseudoachromatic number list-chromatic number rainbow connection number true true false [E. Iršič] Slovenski jezik Angleški jezik Diplomsko delo 2012-07-04 10:05:30 2012-08-02 12:36:30 2022-04-21 14:31:21 2023-12-31 03:31:56 2012 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 19292680 URN:SI:UM:DK:19SLAWUF UNI_Irsic_Eva_2012.pdf UNI_Irsic_Eva_2012.pdf 1 AE239EED086BECE33F553E1DA40152DF c35ce51a826d32e70d8403e93f3d914903d593a599855ce7a3af3c02a15b0592 97a6c649-7c06-11eb-bb7a-00155d0001ca 20.500.12556/dkum/7e30d06a-5855-4165-8600-4358d1c93835 https://dk.um.si/Dokument.php?lang=slv&id=48240 Fakulteta za naravoslovje in matematiko 0 0 0