izpis_h1_title_alt

Pakirno kromatično število koron nad potmi in cikli : delo diplomskega seminarja
ID Robba, Barbara (Author), ID Klavžar, Sandi (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (428,64 KB)
MD5: 066F48D5BAA6075F050F6ED4A6C88BEC

Abstract
Pakirno kromatično število $\chi_{\pi}(G)$ grafa $G$ je najmanjši $k$, za katerega lahko poiščemo $k$-pakirno barvanje grafa, torej najmanjši $k$, za katerega obstaja taka funkcija $\pi: (G) \to [k]$, da iz $\pi(u) = \pi(v)$ sledi, da je razdalja med $u$ in $v$ večja od $\pi(u)$. Za graf $G$ in $p \ge 1$ definiramo $p$-korono grafa $G$ kot graf, ki ga iz grafa $G$ dobimo tako, da na vsako njegovo vozlišče pripnemo $p$ dodatnih listov (torej vozlišč stopnje ena). Določanje pakirnega kromatičnega števila grafa je v splošnem težek problem, kar v delu nakažemo s tem, da dokažemo, da je 4-pakirno barvanje NP-poln problem. Nato dokažemo izrek o pakirnem kromatičnem številu na poteh in ciklih, zatem pa se omejimo na pakirno kromatično število $p$-koron poti in ciklov.

Language:Slovenian
Keywords:pakirno barvanje, pakirno kromatično število, korona grafa, pot, cikel
Work type:Final seminar paper
Organization:FMF - Faculty of Mathematics and Physics
Year:2019
PID:20.500.12556/RUL-110233 This link opens in a new window
UDC:519.1
COBISS.SI-ID:18725465 This link opens in a new window
Publication date in RUL:13.09.2019
Views:1202
Downloads:194
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Packing Chromatic Number of Coronae of Paths and Cycles
Abstract:
The packing chromatic number $\chi_{\pi}(G)$ of a graph $G$ is the smallest integer $k$ for which a packing k-coloring of graph $G$ can be found, which is the smallest $k$ for which such a function $\pi: (G) \to [k]$ exists, that from $\pi(u) = \pi(v)$ follows that the distance between u and v is greater than $\pi(u)$. For a graph $G$ and $p \ge 1$, a $p$-coronae of the graph $G$ is defined as the graph we obtain graph $G$ by adding p additional leaves (vertices of degree 1) to each vertex on the graph. Determining the packing chromatic number of a graph is a complex problem. In this paper we show this by presenting a proof that 4-packing coloring is an NP-complete problem. Then we prove a theorem on the packing chromatic number of paths and cycles, and afterwards focus on the packing chromatic number of $p$-coronae of paths and cycles.

Keywords:packing coloring, packing chromatic number, corona graph, path, cycle

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back