Locirajoče kromatično število grafa

Unuk, Karmen

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Locirajoče kromatično število grafa
Authors:	ID Unuk, Karmen (Author) ID Jakovac, Marko (Mentor) More about this mentor...
Files:	UN_Unuk_Karmen_2015.pdf (1,00 MB) MD5: A5CBEF408D1273F0337BC33FDA333ACE
Language:	Slovenian
Work type:	Undergraduate thesis
Typology:	2.11 - Undergraduate Thesis
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	V diplomskem delu je obravnavano locirajoče kromatično število grafa. Za barvanje $c$ povezanega grafa $G$ naj bo $pi=(C_1,C_2, ldots ,C_k)$ urejena particija množice vozlišč $V(G)$ glede na barvanje $c$. Za vozlišče $v$ grafa $G$ je barvna koda $c_{pi}(v)$ vozlišča $v$ urejena $k$-terica $(d(v,C_1),d(v,C_2), ldots ,d(v,C_k))$, kjer je $d(v,C_i)=min{d(v,x)\|x in C_i}$, za $i in {1, ldots ,k}$. Če imata različni vozlišči različni barvni kodi, potem $c$ imenujemo locirajoče barvanje. Locirajoče kromatično število, $chi_L(G)$, je najmanjše število barv, potrebnih za locirajoče barvanje grafa $G$. Meje za locirajoče kromatično število povezanega grafa so ugotovljene s stališča njegovega reda in premera. Določeni so vsi povezani grafi reda $n geq 3$ z locirajočim kromatičnim številom $n$. Pokazano je, da za vsak par naravnih števil $a,b geq 2$ obstaja povezan graf s kromatičnim številom $a$ in locirajočim kromatičnim številom $b$. Določeno je locirajoče kromatično število nekaterih znanih grafov. Posebej je predstavljeno locirajoče kromatično število dreves.
Keywords:	locirajoče barvanje, locirajoče kromatično število
Place of publishing:	Maribor
Publisher:	[K. Unuk]
Year of publishing:	2015
PID:	20.500.12556/DKUM-47764-45073742-9aee-e835-6bf7-e6e8675a9f49
UDC:	519.17(043.2)
COBISS.SI-ID:	21310472
NUK URN:	URN:SI:UM:DK:AESUA0DR
Publication date in DKUM:	21.04.2015
Views:	1510
Downloads:	152
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:	The locating-chromatic number of a graph
Abstract:	In this graduation thesis locating-chromatic number of a graph will be discussed. For a coloring $c$ of a connected graph $G$, let $pi=(C_1,C_2, ldots ,C_k)$ be an ordered partition of $V(G)$ with respect to the coloring $c$. For a vertex $v$ of $G$, the color code $c_{pi}(v)$ of $v$ is the ordered $k$-tuple $(d(v,C_1),d(v,C_2), ldots ,d(v,C_k))$, where $d(v,C_i)=min{d(v,x)\|x in C_i}$ for $i in {1, ldots ,k}$. If distinct vertices have distinct color codes, then $c$ is called a locating-coloring. The locating-chromatic number $chi_L(G)$ is the minimum number of colors in a locating-coloring of $G$. Bounds for the locating-chromatic number of a connected graph are established in terms of its order and diameter. All connected graphs of order $n geq 3$ with locating-chromatic number $n$ are determined. It is shown that for each pair $a,b$ of integers with $a,b geq 2$ there exists a connected graph with chromatic number $a$ and locating-chromatic number $b$. The locating-chromatic number of some well-known graph classes is determined, and the locating-chromatic number of trees is studied.
Keywords:	locating-coloring, locating-chromatic number

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back