Journal of Combinatorics
Volume 9 (2018)
Monochromatic homeomorphically irreducible trees in $2$-edge-colored complete graphs
Pages: 681 – 691
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$.
homeomorphically irreducible spanning tree, $2$-edge-colored complete graph
2010 Mathematics Subject Classification
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