Journal of Combinatorics

Volume 9 (2018)

Number 4

Monochromatic homeomorphically irreducible trees in $2$-edge-colored complete graphs

Pages: 681 – 691

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a6

Authors

Michitaka Furuya (College of Liberal Arts and Sciences, Kitasato University, Sagamihara, Kanagawa, Japan)

Shoichi Tsuchiya (School of Network and Information, Senshu University, Kawasaki-shi, Kanagawa, Japan)

Abstract

It has been known that every $2$-edge-colored complete graph has a monochromatic connected spanning subgraph. In this paper, we study a condition which can be imposed on such a monochromatic subgraph, and show that almost all $2$-edge-colored complete graphs have a monochromatic spanning tree with no vertices of degree $2$. As a corollary of our main theorem, we obtain a Ramsey type result: Every $2$-edge-colored complete graph of order $n \geq 8$ has a monochromatic tree $T$ with no vertices of degree $2$ and $\lvert V (T) \rvert \geq n-1$.

Keywords

homeomorphically irreducible spanning tree, $2$-edge-colored complete graph

2010 Mathematics Subject Classification

05C38, 05C45

Full Text (PDF format)

This research was partially supported by JSPS KAKENHI Grant number 26800086 (to M.F), JSPS KAKENHI Grant number JP16K17646 (to S.T) and research grant of Senshu University (to S.T).

Received 16 March 2017

Published 7 December 2018