-
A planar linear arboricity conjectureCygan, Marek ...Linearna razvejanost ▫${\rm la}(G)$▫ grafa ▫$G$▫ je najmanjše število linearnih gozdov (grafov, v katerih je vsaka povezana komponenta pot), ki delijo povezave ▫$G$▫. Leta 1984 so Akiyama et al. ... podali hipotezo o linearni razvejanosti (Linear Arboricity Conjecture (LAC)), ki pravi, da je linearna razvejanost poljubnega enostavnega grafa z maksimalno stopnjo ▫$\Delta$▫ ali ▫$\big \lceil \tfrac{\Delta}{2} \big \rceil$ ali $\big \lceil \tfrac{\Delta+1}{2} \big \rceil$▫. Dokazano je že, da LAC drži za vse ravninske grafe. Iz LAC sledi, da za lihe ▫$\Delta$▫ velja ▫${\rm la}(G)=\big \lceil \tfrac{\Delta}{2} \big \rceil$▫. V članku postavimo hipotezo, ki pravi, da je zgornja enakost resnična tudi za vse sode ▫$\Delta \ge 6$▫. Dokazali smo, da drži za vse sode ▫$\Delta \ge 10$▫. Odprto ostane vprašanje za ▫$\Delta=6, 8$▫. Predstavimo tudi algoritem s časovno zahtevnostjo ▫$O(n\log n)$▫, ki razdeli ravninski graf na ▫$\max\{{\rm la}(G), 5\}$▫ linearnih gozdov, ki je optimalen za ▫$\Delta \ge 9$▫.Source: Journal of graph theory. - ISSN 0364-9024 (Vol. 69, no. 4, 2012, str. 403-425)Type of material - article, component partPublish date - 2012Language - englishCOBISS.SI-ID - 16243289
Author
Cygan, Marek |
Hou, Jian-Feng |
Kowalik, Łukasz |
Lužar, Borut |
Wu, Jian-Liang
Topics
teorija grafov |
linearna razvejanost |
▫$t$▫-linearno barvanje |
LAC hipoteza |
ravninski graf |
metoda prenosa naboja |
graph theory |
linear arboricity |
▫$t$▫-linear coloring |
LAC conjecture |
planar graph |
discharging method
![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 |
---|---|
Cygan, Marek | ![]() |
Hou, Jian-Feng | ![]() |
Kowalik, Łukasz | ![]() |
Lužar, Borut | 31670 |
Wu, Jian-Liang | ![]() |
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.