-
List-coloring squares of sparse subcubic graphsDvořák, Zdeněk ; Škrekovski, Riste ; Tancer, MartinProblem barvanja kvadrata grafa je v tesni zvezi z razdaljnim označevanjem grafov, ki je predmet intenzivnega raziskovanja v zadnjem času. Problem obravnavamo na redkih subkubičnih grafih. Pokažemo, ... da je izbirljivost ▫$\chi_\ell(G^2)$▫ kvadrata subkubičnega grafa z maksimalno povprečno stopnjo ▫$d$▫ največ 4, če je ▫$d < 24/11$▫ in ▫$G$▫ ne vsebuje 5-ciklov, ▫$\chi_\ell(G^2)$▫ je največ 5 za ▫$d < 7/3$▫ in je največ 6 za ▫$d < 5/2$▫. Wegnerjeva hipoteza trdi, da je kromatično število kvadrata subkubičnega ravninskega grafa največ 7. Naj bo ▫$G$▫ ravninski graf z notranjim obsegom ▫$g$▫. Iz našega rezultata sledi, da je ▫$\chi_\ell(G^2)$▫ največ 4 za ▫$g \ge 24$▫, največ 5 za ▫$g \ge 14$▫ in največ 6 za ▫$g \ge 10$▫. Določili smo spodnji meji: ravninski subkubični graf ▫$G_1$▫ z notranjim obsegom 9 in ▫$\chi(G_1^2) = 5$▫ ter ravninski subkubični graf ▫$G_2$▫ z notranjim obsegom 5 in ▫$\chi(G_2^2) = 6$▫. Posledično dokažemo, da je problem 4-barvanja kvadrata subkubičnega ravninskega grafa z notranjim obsegom ▫$g=9$▫ NP-težek problem. Članek zaključimo z nekaj odprtimi vprašanji.Source: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 22, no. 1, 2008, str. 139-159)Type of material - article, component partPublish date - 2008Language - englishCOBISS.SI-ID - 14656857
Author
Dvořák, Zdeněk |
Škrekovski, Riste |
Tancer, Martin
Topics
matematika |
teorija grafov |
seznamsko barvanje |
redek graf |
kvadrat grafa |
kubični graf |
ravninski graf |
mathematics |
graph theory |
planar graphs |
sparse graphs |
list coloring |
complexity |
square of graph |
cubic graph |
planar graph |
NP-complete
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dvořák, Zdeněk | ![]() |
Škrekovski, Riste | 15518 |
Tancer, Martin | ![]() |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.