Premium
The minimum degree of Ramsey‐minimal graphs
Author(s) -
Fox Jacob,
Lin Kathy
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20199
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , discrete mathematics , induced subgraph , degree (music) , vertex connectivity , monochromatic color , physics , acoustics , optics
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 ( K k ) = ( k − 1) 2 and s ( K a,b ) = 2 min( a,b ) − 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007