| Identifikační kód | RIV/00216224:14330/15:00080985 |
|---|
| Název v anglickém jazyce | On Degree Properties of Crossing-critical Families of Graphs |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Drago Bokal (státní příslušnost: SI - Slovinská republika)
Mojca Bračič (státní příslušnost: SI - Slovinská republika)
Marek Derňár (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 4464737)
Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) |
|---|
| Popis výsledku v anglickém jazyce | Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that min(D)>=3 and 3,4eD, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families. |
|---|
| Klíčová slova oddělená středníkem | Crossing number; Tile drawing; Degree-universality; Average degree; Crossing-critical graph |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-319-27261-0_7 |
|---|