On the geometric Ramsey numbers of trees

From MaRDI portal

(Redirected from Publication:501079)

Jump to:navigation, search

DOI10.1016/J.DISC.2015.08.021MaRDI QIDQ501079zbMATH OpenOpenAlexFDO

Authors Pu Gao

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.5188

zbMATH Keywords

outerplanar graph caterpillar geometric Ramsey number pathwidth-2 outerplanar triangulation

Mathematics Subject Classification ID

Trees (05C05) Generalized Ramsey theory (05C55)

Abstract: In this paper, we obtain upper bounds for the geometric Ramsey numbers of trees. We prove that

R_{c} (T_{n}, H_{m}) = (n - 1) (m - 1) + 1

if

T_{n}

is a caterpillar and

H_{m}

is a Hamiltonian outerplanar graph on

m

vertices. Moreover, if

T_{n}

has at most two non-leaf vertices, then

R_{g} (T_{n}, H_{m}) = (n - 1) (m - 1) + 1

. We also prove that

R_{c} (T_{n}, H_{m}) = O (n^{2} m)

and

R_{g} (T_{n}, H_{m}) = O (n^{3} m^{2})

if

T_{n}

is an arbitrary tree on

n

vertices and

H_{m}

is an outerplanar triangulation with pathwidth 2. %Further, we prove a uniform polynomial upper bound for the geometric Ramsey numbers of caterpillars and we also give an upper bound for

R_{g} (T_{n})

where

T_{n}

is an arbitrary tree.

Recommendations

Cites work

Cited in

(1)

On the geometric Ramsey number of outerplanar graphs

This page was built for publication: On the geometric Ramsey numbers of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501079)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=On_the_geometric_Ramsey_numbers_of_trees&oldid=62389551"