Thrackles: An Improved Upper Bound
| Autor: | Radoslav Fulek, János Pach |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
060201 languages & linguistics
Combinatorics Thrackle 0602 languages and literature 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 06 humanities and the arts 02 engineering and technology Upper and lower bounds Graph Vertex (geometry) Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319739144 Graph Drawing |
| DOI: | 10.1007/978-3-319-73915-1_14 |
| Popis: | A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is \({3\over 2}(n-1)\), and that this bound is best possible for infinitely many values of n. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|