pith. machine review for the scientific record. sign in

arxiv: 1803.04889 · v1 · submitted 2018-03-13 · 🧮 math.CO

Recognition: unknown

Planar anti-Ramsey numbers of matchings

Authors on Pith no claims yet
classification 🧮 math.CO
keywords mathcalplanaranti-ramseycontainslowermatchingsnumbernumbers
0
0 comments X
read the original abstract

Given a positive integer $n$ and a planar graph $H$, let $\mathcal{T}_n(H)$ be the family of all plane triangulations $T$ on $n$ vertices such that $T$ contains a subgraph isomorphic to $H$. The planar anti-Ramsey number of $H$, denoted $ar_{_\mathcal{P}}(n, H)$, is the maximum number of colors in an edge-coloring of a plane triangulation $T\in \mathcal{T}_n(H)$ such that $T$ contains no rainbow copy of $H$. In this paper we study planar anti-Ramsey numbers of matchings. For all $t\ge1$, let $M_t$ denote a matching of size $t$. We prove that for all $t\ge6$ and $n\ge 3t-6$, $2n+3t-15\le ar_{_{\mathcal{P}}}(n, {M}_t)\le 2n+4t-14$, which significantly improves the existing lower and upper bounds for $ar_{_\mathcal{P}}(n, M_t)$. It seems that for each $t\ge6$, the lower bound we obtained is the exact value of $ar_{_{\mathcal{P}}}(n, {M}_t)$ for sufficiently large $n$. This is indeed the case for $M_6$. We prove that $ar_{_\mathcal{P}}(n, M_6)=2n+3$ for all $n\ge30$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.