# Pakirno kromatično število koron nad potmi in cikli : delo diplomskega seminarja
Robba, Barbara (Avtor), Klavžar, Sandi (Mentor) Več o mentorju...  PDF - Predstavitvena datoteka, prenos (428,64 KB)MD5: 066F48D5BAA6075F050F6ED4A6C88BEC

Izvleček
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.

Jezik: Slovenski jezik pakirno barvanje, pakirno kromatično število, korona grafa, pot, cikel Delo diplomskega seminarja/zaključno seminarsko delo/naloga (mb14) FMF - Fakulteta za matematiko in fiziko 2019 519.1 18725465 470 154    (0 glasov) Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.Uredi privoljenje...

## Sekundarni jezik

Jezik: Angleški jezik Packing Chromatic Number of Coronae of Paths and Cycles 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. packing coloring, packing chromatic number, corona graph, path, cycle

## Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
 0 - 0 / 0 Ni komentarjev!

Nazaj