Pakirno kromatično število koron nad potmi in cikli : delo diplomskega seminarja

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 pakirno barvanje, pakirno kromatično število, korona grafa, pot, cikel Final seminar paper (mb14) FMF - Faculty of Mathematics and Physics 2019 519.1 18725465 164 52 (0 votes) Voting is allowed only to logged in users. AddThis uses cookies that require your consent. Edit consent...

## Secondary language

Language: English 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

Leave comment