| Title: | On the packing chromatic number of Cartesian products, hexagonal lattice, and trees |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Klavžar, Sandi (Author)
ID Rall, Douglas F. (Author) |
|---|
| Files: |  http://dx.doi.org/10.1016/j.dam.2007.06.008
|
|---|
| Language: | English |
|---|
| Work type: | Not categorized |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| Abstract: | Pakirno kromatično število ▫$chi_{rho}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v pakiranja s paroma različnimi širinami. Dobljenih je več spodnjih in zgornjih meja za pakirno kromatično število kartezičnega produkta grafov. Dokazano je, da pakirno kromatično število šestkotniške mreže leži med 6 in 8. Optimalne spodnje in zgornje meje so dokazane za subdividirane grafe. Obravnavana so tudi drevesa ter vpeljana monotona barvanja. |
|---|
| Keywords: | matematika, teorija grafov, pakirno kromatično število, kartezični produkt grafov, šestkotniška mreža, subdividiran graf, drevo, računska zahtevnost, mathematics, graph theory, packing chromatic number, Cartesian product of graphs, hexagonal lattice, subdivision graph, tree, computational complexity |
|---|
| Year of publishing: | 2007 |
|---|
| Number of pages: | str. 2003-2311 |
|---|
| Numbering: | Vol. 155, iss. 17 |
|---|
| PID: | 20.500.12556/DKUM-51602  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0166-218X |
|---|
| COBISS.SI-ID: | 14418009 |
|---|
| NUK URN: | URN:SI:UM:DK:WWFHJIXC |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1525 |
|---|
| Downloads: | 168 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
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. |
