delo diplomskega seminarja
Barbara Robba (Avtor), Sandi Klavžar (Mentor)

Povzetek

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.

Ključne besede

matematika;pakirno barvanje;pakirno kromatično število;korona grafa;poti;cikli;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [B. Robba]
UDK: 519.1
COBISS: 18725465 Povezava se bo odprla v novem oknu
Št. ogledov: 1362
Št. prenosov: 198
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Packing Chromatic Number of Coronae of Paths and Cycles
Sekundarni povzetek: 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.
Sekundarne ključne besede: mathematics;packing coloring;packing chromatic number;corona graph;paths;cycles;
Vrsta dela (COBISS): Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program: 0
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani: 26 str.
ID: 11222789