-
A relaxed Hadwiger's Conjecture for list coloringKawarabayashi, Ken-ichi ; Mohar, Bojan, 1956-Hadwigerjeva hipoteza trdi, da se da vsak graf, ki ne vsebuje polnega grafa ▫$K_k$▫ kot minorja, obarvati s ▫$k-1$▫ barvami. Domneva je dokazana za ▫$k \le 6$▫ in odprta za večje vrednosti. Ni znano ... niti to, če obstaja taka konstanta ▫$c$▫,da se da vsak graf brez minorja ▫$K_k$▫ obarvati s ▫$ck$▫ barvami. V članku je dokazano, da obstaja taka eksplicitna konstanta ▫$f(k)$▫, da lahko vozlišca vsakega grafa brez minorja ▫$K_k$▫ razbijemo na bloke ▫$V_1,...,V_{\lceil 15.5k \rceil}$▫, tako da ima vsaka komponenta podgrafa induciranega na ▫$V_i$▫ ▫($i \ge 1)$▫ kvečjemu ▫$f(k)$▫ vozlišč. Ta rezultat je posplošen na seznamska barvanja, kjer zahtevamo, da imajo enobarvne komponente kvečjemu ▫$f(k)$▫ vozlišč.Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 97, iss. 4, 2007, str. 647-651)Type of material - article, component partPublish date - 2007Language - englishCOBISS.SI-ID - 14377817
Author
Kawarabayashi, Ken-ichi |
Mohar, Bojan, 1956-
Topics
matematika |
teorija grafov |
seznamsko barvanje |
minor grafa |
povezanost |
drevesna širina |
Hadwigerjeva hipoteza |
▫$k$▫-prepleteni graf |
grafi na ploskvah |
mathematics |
graph theory |
list coloring |
graph minor |
connectivity |
tree-width |
▫$k$▫-linked |
Hadwiger conjecture |
grid minor |
near embedding |
graphs on surfaces |
list colorings
source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 97, iss. 4, 2007, str. 647-651)
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 |
---|---|
Kawarabayashi, Ken-ichi | |
Mohar, Bojan, 1956- | 01931 |
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.