-
Nordhaus-Gaddum-type theorems for decompositions into many partsFüredi, Zoltán ...▫$k$▫-terica ▫$(G_1,...,G_k)$▫ vpetih podgrafov grafa ▫$G$▫ je ▫$k$▫-dekompozicija, če množice povezav teh podgrafov tvorijo razbitje množice ▫$E(G)$▫. Izrek Nordhausa in Gadduna poda meje za ... ▫$\chi(G_1) + \chi(G_2)$▫ in ▫$\chi(G_1) \chi(G_2)$▫ za vse 2-dekompozicije grafa ▫$G$▫. Za grafovski parameter ▫$p$▫ naj bo ▫$p(k;G)$▫ maksimum vsote ▫$\sum_{i=1}^{k}p(G_i)$▫ čez vse ▫$k$▫-dekompozicije grafa ▫$G$▫. Za klično število ▫$\omega$▫, kromatično število ▫$\chi$▫, seznamsko število ▫$\chi_{\ell}$▫ ter Szekeres-Wilfovo število ▫$\sigma$▫ velja ▫$\omega(2;K_n) = \chi(2;K_n) = \chi_\ell (2;K_n) = \sigma(2;K_n) = n + 1$▫. V članku so podane zgornje in spodnje meje za ▫$\omega(k;K_n)$▫, ▫$\chi(k;K_n)$▫, ▫$\chi_\ell(k;K_n)$▫ in ▫$\sigma(k;K_n)$▫. Zadnje tri se obnašajo različno za velike ▫$k$▫. Podani sta tudi zgornja in spodnja meja za maksimum ▫$\chi(k;G)$▫ čez vse grafe vložene na dano ploskev.Source: Journal of graph theory. - ISSN 0364-9024 (Vol. 50, no. 4, 2005, str. 273-292)Type of material - article, component partPublish date - 2005Language - englishCOBISS.SI-ID - 13791321
Author
Füredi, Zoltán |
Kostochka, Alexandr V. |
Škrekovski, Riste |
Stiebitz, Michael |
West, Douglas Brent
Topics
matematika |
teorija grafov |
dekompozicija |
barvanja grafa |
mathematics |
graph theory |
graph decomposition |
Nordhaus-Gaddum theorem |
chromatic number |
coloring number |
list chromatic number |
surface embedding
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 |
---|---|
Füredi, Zoltán | |
Kostochka, Alexandr V. | |
Škrekovski, Riste | 15518 |
Stiebitz, Michael | |
West, Douglas Brent |
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.