All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 5 Next

Displaying 81 – 100 of 141

Showing per page

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2015)

Annales UMCS, Mathematica

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case...

On Ramsey ( K 1 , 2 , C ₄ ) -minimal graphs

Tomás Vetrík, Lyra Yulianti, Edy Tri Baskoro (2010)

Discussiones Mathematicae Graph Theory

For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey ( K 1 , 2 , C ₄ ) -minimal graphs of any diameter ≥ 4.

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring...

On the Vertex Folkman Numbers Fv(2,...,2;q)

Nenov, Nedyalko (2009)

Serdica Mathematical Journal

2000 Mathematics Subject Classification: 05C55.In this paper we shall compute the Folkman numbers ... We prove also new bounds for some vertex and edge Folkman numbers.

One More Turán Number and Ramsey Number for the Loose 3-Uniform Path of Length Three

Joanna Polcyn (2017)

Discussiones Mathematicae Graph Theory

Let P denote a 3-uniform hypergraph consisting of 7 vertices a, b, c, d, e, f, g and 3 edges {a, b, c}, {c, d, e}, and {e, f, g}. It is known that the r-color Ramsey number for P is R(P; r) = r + 6 for r ≤ 9. The proof of this result relies on a careful analysis of the Turán numbers for P. In this paper, we refine this analysis further and compute the fifth order Turán number for P, for all n. Using this number for n = 16, we confirm the formula R(P; 10) = 16.

On-line Ramsey theory.

Grytczuk, J.A., Hałuszczak, M., Kierstead, H.A. (2004)

The Electronic Journal of Combinatorics [electronic only]

Planar Ramsey numbers

Izolda Gorgol (2005)

Discussiones Mathematicae Graph Theory

The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.

Currently displaying 81 – 100 of 141