PhD Defense: Generalized Ramsey Numbers for Graphs

When: March 13, 2015, 16:30-18:30

Where: Prof. Dr. G. Berkhoff-zaal- Waaier building

Who: Yanbo Zhang

This thesis contains new contributions to Ramsey theory, in particular results that establish exact values of graph Ramsey numbers that were unknown to date. Given two graphs F and H, the Ramsey number R(F,H) is the smallest integer N such that, for any graph G of order N, either G contains F as a subgraph, or the complement of G contains H as a subgraph.

Burr showed back in 1984 that the problem of determining the exact value of R(F,H) for arbitrary graphs F and H is NP-hard. Using techniques and results from graph theory, since the early 1970s researchers have been trying to confirm the exact value of Ramsey numbers for many well-studied families of graphs, including cycles, wheels, stars, paths, trees, fans and kipases. This is the main motivation and approach behind most of the results in this thesis.

The thesis contains nine chapters with new results (Chapters 2–10), together with an introductory chapter (Chapter 1). The first three of these chapters (Chapters 2, 3 and 4) deal with Ramsey numbers for cycles versus stars or wheels. The next four chapters involve Ramsey numbers for trees versus fans or wheels (Chapter 5), fans versus fans, wheels or complete graphs (Chapter 6), paths versus kipases (Chapter 7), and the union of some graphs (Chapter 8). We study planar Ramsey numbers in Chapter 9, star-critical and upper size Ramsey numbers in Chapter 10.

	Home > News and Events > Events
<< EEMCS (EWI) Home News and Events » Group Colloquium » Events » In the Media People Research Education Vacancies Intranet Contact	PhD Defense: Generalized Ramsey Numbers for Graphs When: March 13, 2015, 16:30-18:30 Where: Prof. Dr. G. Berkhoff-zaal- Waaier building Who: Yanbo Zhang This thesis contains new contributions to Ramsey theory, in particular results that establish exact values of graph Ramsey numbers that were unknown to date. Given two graphs F and H, the Ramsey number R(F,H) is the smallest integer N such that, for any graph G of order N, either G contains F as a subgraph, or the complement of G contains H as a subgraph. Burr showed back in 1984 that the problem of determining the exact value of R(F,H) for arbitrary graphs F and H is NP-hard. Using techniques and results from graph theory, since the early 1970s researchers have been trying to confirm the exact value of Ramsey numbers for many well-studied families of graphs, including cycles, wheels, stars, paths, trees, fans and kipases. This is the main motivation and approach behind most of the results in this thesis. The thesis contains nine chapters with new results (Chapters 2–10), together with an introductory chapter (Chapter 1). The first three of these chapters (Chapters 2, 3 and 4) deal with Ramsey numbers for cycles versus stars or wheels. The next four chapters involve Ramsey numbers for trees versus fans or wheels (Chapter 5), fans versus fans, wheels or complete graphs (Chapter 6), paths versus kipases (Chapter 7), and the union of some graphs (Chapter 8). We study planar Ramsey numbers in Chapter 9, star-critical and upper size Ramsey numbers in Chapter 10.