Attributes | Values |
---|
rdf:type
| |
Description
| - The structure of all known infinite families of crossing--critical graphs has led to the conjecture that crossing--critical graphs have bounded bandwidth. If true, this would imply that crossing--critical graphs have bounded degree, that is, that they cannot contain subdivisions of $K_{1,n}$ for arbitrarily large $n$. In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing--critical graphs cannot contain subdivisions of $K_{2,n}$ for arbitrarily large $n$. On the negative side, we show that there are graphs with arbitrarily large maximum degree that are $2$-crossing--critical in the projective plane.
- The structure of all known infinite families of crossing--critical graphs has led to the conjecture that crossing--critical graphs have bounded bandwidth. If true, this would imply that crossing--critical graphs have bounded degree, that is, that they cannot contain subdivisions of $K_{1,n}$ for arbitrarily large $n$. In this paper we prove two results that revolve around this conjecture. On the positive side, we show that crossing--critical graphs cannot contain subdivisions of $K_{2,n}$ for arbitrarily large $n$. On the negative side, we show that there are graphs with arbitrarily large maximum degree that are $2$-crossing--critical in the projective plane. (en)
- Prezentujeme dva přístupy k dosud otevřené domněnce, že průsečíkově kritické grafy mají omezený maximální stupeň. Na pozitivní straně dokazujeme, že tyto grafy nemohou obsahovat subdivizi velkého K_2,n, ale na negativní straně ukazujeme neplatnost domněnky v projektivní rovině. (cs)
|
Title
| - Stars and Bonds in Crossing-Critical Graphs
- Stars and Bonds in Crossing-Critical Graphs (en)
- Hvězdy a řezy v průsečíkově kritických grafech (cs)
|
skos:prefLabel
| - Stars and Bonds in Crossing-Critical Graphs
- Stars and Bonds in Crossing-Critical Graphs (en)
- Hvězdy a řezy v průsečíkově kritických grafech (cs)
|
skos:notation
| - RIV/00216224:14330/08:00024776!RIV09-GA0-14330___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216224:14330/08:00024776
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - crossing number; crossing-critical graph (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| - The International Conference on Topological and Geometric Graph Theory TGGT2008, Electronic Notes in Discrete Mathematics 31, 2008
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| - Hliněný, Petr
- Salazar, Gelasio
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
issn
| |
number of pages
| |
http://purl.org/ne...btex#hasPublisher
| |
http://localhost/t...ganizacniJednotka
| |