Barvanja grafov, ki so brez ponavljanj po licih

Zemljič, Sara Sabrina

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Barvanja grafov, ki so brez ponavljanj po licih
Authors:	ID Zemljič, Sara Sabrina (Author) ID Klavžar, Sandi (Mentor) More about this mentor...
Files:	UNI_Zemljic_Sara_Sabrina_2010.pdf (2,53 MB) MD5: 5158020474F0A82D5EC5AF806ACB9214 PID: 20.500.12556/dkum/d00d8140-6b9d-46b8-b8ef-db705d7821cf
Language:	Slovenian
Work type:	Undergraduate thesis
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	Diplomsko delo obravnava osnovne lastnosti barvanj grafov brez ponavljanj. Osrednja tema je barvanje povezav ravninskih grafov brez ponavljanj po licih. Na začetku diplomskega dela so predstavljene osnovne definicije iz teorije grafov, ki jih bomo potrebovali v nadaljevanju. V drugem poglavju vpeljemo barvanje grafov brez ponavljanj in naredimo pregled nad že znanimi rezultati o teh barvanjih. Na koncu drugega poglavja definiramo barvanje povezav ravninskih grafov brez ponavljanj po licih ter njemu pripadajoč Thuejev lični indeks, ki predstavlja najmanjše število barv, s katerimi lahko pobarvamo graf brez ponavljanj po licih. Tretje poglavje je v celoti namenjeno obravnavi barvanja dreves brez ponavljanj po licih. V tem poglavju dokažemo, da je Thuejev lični indeks dreves kvečjemu 4, kar je osnova za dokaz splošne zgornje meje Thuejevega ličnega indeksa. Na koncu pokažemo, da je Thuejev lični indeks poljubnega ravninskega grafa največ 8. Navedemo še nekaj posebnih družin ravninskih grafov, kjer se ta zgornja meja zmanjša.
Keywords:	barvanje brez ponavljanj, Thuejevo število, Thuejev indeks, ravninski graf, drevo
Place of publishing:	Maribor
Publisher:	[S.S. Zemljič]
Year of publishing:	2010
PID:	20.500.12556/DKUM-15168
UDC:	51(043.2)
COBISS.SI-ID:	17859080
NUK URN:	URN:SI:UM:DK:ZJTPNZB2
Publication date in DKUM:	11.11.2010
Views:	2781
Downloads:	258
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:	English
Title:	Facial non-repetitive colorings of plane graphs
Abstract:	The thesis investigates basic properties of non-repetitive graph colorings. The main theme is facial non-repetitive edge coloring of planar graphs. First we present basic definitions from graph theory. In Section 2 we study non-repetitive colorings of graphs and list already known results about those colorings. At the end of Section 2 we define facial non-repetitive edge coloring of planar graphs and facial Thue index, which represents the minimum number of colors of a facial non-repetitive edge coloring of graph. The third chapter is entirely devoted to facial non-repetitive edge coloring of trees. In this section we prove that facial Thue index of a tree is at most 4, which is the basis for a proof of general upper bound on facial Thue index. Finally, we show that the facial Thue index of an arbitrary plane graph is at most 8. We also show that for some specific families of planar graphs this upper bound can be reduced.
Keywords:	non-repetitive coloring, Thue number, Thue index, plane graph, tree

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back