| | |
| | |
Stat |
Members: 3645 Articles: 2'501'711 Articles rated: 2609
20 April 2024 |
|
| | | |
|
Article overview
| |
|
On topological graphs with at most four crossings per edge | Eyal Ackerman
; | Date: |
7 Sep 2015 | Abstract: | We show that if a graph $G$ with $n geq 3$ vertices can be drawn in the
plane such that each of its edges is involved in at most four crossings, then
$G$ has at most $6n-12$ edges. This settles a conjecture of Pach,
Radoiv{c}i’{c}, Tardos, and T’oth, and yields a better bound for the famous
Crossing Lemma: The crossing number, $mbox{cr}(G)$, of a (not too sparse)
graph $G$ with $n$ vertices and $m$ edges is at least $cfrac{m^3}{n^2}$, where
$c > 1/29$. This bound is known to be tight, apart from the constant $c$ for
which the previous best lower bound was $1/31.1$. As another corollary we
obtain some progress on the Albertson conjecture: Albertson conjectured that if
the chromatic number of a graph $G$ is $r$, then $mbox{cr}(G) geq
mbox{cr}(K_r)$. This was verified by Albertson, Cranston, and Fox for $r leq
12$, and for $r leq 16$ by Bar’at and T’oth. Our results imply that
Albertson conjecture holds for $r leq 18$. | Source: | arXiv, 1509.1932 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |