Izreki Nordhaus-Gaddumovega tipa za nekatere kromatične invariante

diplomsko delo

Eva Iršič (Author), Marko Jakovac (Mentor)

Abstract

Diplomskp delo obravnava izreke Nordhaus-Gaddumovega tipa za nekatere kromatične invariante. Na začetku predstavimo osnovne pojme teorije grafov, ki so potrebni za razumevanje nadaljnje snovi. V delo 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.

Keywords

matematika;števila;povezanosti;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2012
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[E. Iršič]
UDC:	51(043.2)
COBISS:	19292680
Views:	1447
Downloads:	102
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	NORDHAUS-GADDUM TYPE THEOREMS FOR SOME CHROMATIC INVARIANTS
Secondary abstract:	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.
Secondary keywords:	chromatic number;achromatic number;pseudoachromatic number;list-chromatic number;rainbow connection number;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	45 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	1026181