The minimum degree of Ramsey‐minimal graphs
Open Access
- 16 November 2006
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 54 (2) , 167-177
Abstract
We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ↛ G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(Kk) = (k − 1)2 and s(Ka,b) = 2 min(a,b) − 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007Keywords
This publication has 6 references indexed in Scilit:
- Non-Ramsey Graphs Are clogn-UniversalJournal of Combinatorial Theory, Series A, 1999
- On nearly regular co-critical graphsDiscrete Mathematics, 1996
- The Ramsey property for graphs with forbidden complete subgraphsJournal of Combinatorial Theory, Series B, 1976
- On multicolor Ramsey numbers for complete bipartite graphsJournal of Combinatorial Theory, Series B, 1975
- On edgewise 2-colored graphs with monochromatic triangles and containing no complete hexagonJournal of Combinatorial Theory, 1968
- Some remarks on the theory of graphsBulletin of the American Mathematical Society, 1947