Some infinite families of Ramsey $(P_{3}, P_{n})$-minimal trees

Proceedings of the Indian Academy of Sciences. Mathematical sciences

D RAHMADANI^1¹  E T BASKORO^1² 

[1] Combinatorial Mathematics Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung (ITB), Bandung, Indonesia^1;Department of Applied Mathematics and Informatics, Technical University, Kosice, Slovak Republic^2

关键词: Ramsey minimal graph;    coloring;    Ramsey infinite;    tree;   

DOI  :  

学科分类：数学（综合）

来源: Indian Academy of Sciences

【 摘 要 】

For any given two graphs G and H, the notation $F \rightarrow (G, H)$ means that for any red–blue coloring of all the edges of $F$ will create either a red subgraph isomorphic to $G$ or a blue subgraph isomorphic to $H$. A graph $F$ is a Ramsey $(G, H)$-minimal graph if $F \rightarrow (G, H)$ but $F − e \nrightarrow (G, H)$, for every $e \in E(F)$. The class of all Ramsey $(G, H)$-minimal graphs is denoted by $\mathcal{R}(G, H)$. In this paper, we construct some infinite families of trees belonging to $\mathcal{R}(P_{3}, P_{n})$, for $n = 8$ and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to $\mathcal{R}(P_{3}, P_{n})$, for $n \geq 10$.

【 授权许可】

CC BY