| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
18 February 2025 |
|
| | | |
|
Article overview
| |
|
Large Matchings in Maximal 1-planar graphs | Therese Biedl
; John Wittnebel
; | Date: |
4 Jan 2023 | Abstract: | It is well-known that every maximal planar graph has a matching of size at
least $ frac{n+8}{3}$ if $ngeq 14$. In this paper, we investigate similar
matching-bounds for maximal emph{1-planar} graphs, i.e., graphs that can be
drawn such that every edge has at most one crossing. In particular we show that
every 3-connected simple-maximal 1-planar graph has a matching of size at least
$ frac{2n+6}{5}$; the bound decreases to $ frac{3n+14}{10}$ if the graph need
not be 3-connected. We also give (weaker) bounds when the graph comes with a
fixed 1-planar drawing or is not simple. All our bounds are tight in the sense
that some graph that satisfies the restrictions has no bigger matching. | Source: | arXiv, 2301.01394 | 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.
|
| |
|
|
|