✦ LIBER ✦

The minimum degree of Ramsey-minimal graphs

✍ Scribed by Jacob Fox; Kathy Lin

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 144 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20199

No coin nor oath required. For personal study only.

✦ Synopsis

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(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

📜 SIMILAR VOLUMES

On the minimum degree of minimal Ramsey

On the minimum degree of minimal Ramsey graphs

✍ Tibor Szabó; Philipp Zumstein; Stefanie Zürcher 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract We investigate the minimization problem of the minimum degree of minimal Ramsey graphs, initiated by Burr et al. We determine the corresponding graph parameter for numerous bipartite graphs, including bi‐regular bipartite graphs and forests. We also make initial progress for graphs of l

Subdivisions of graphs with large minimu

Subdivisions of graphs with large minimum degree

✍ Carsten Thomassen 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 1 views

Graph decomposition with constraints on

Graph decomposition with constraints on the connectivity and minimum degree

✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract For each pair __s,t__ of natural numbers there exist natural numbers __f(s,t)__ and __g(s,t)__ such that the vertex set of each graph of connectivity at least __f(s,t)__ (respectively minimum degree at least __g(s,t))__ has a decomposition into sets which induce subgraphs of connectivit

Light subgraphs in planar graphs of mini

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9

✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

Generalized Ramsey theory for graphs IV,

Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph

✍ F. Harary; G. Prins 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 412 KB

A paopm graph G has no isolated points. I t s R m e y r u m b a r ( G ) i s the m i n i m p such that every 2-coloring of the edges of K contains a monochromatic G. The Ramhey m & t @ m y R(G) i s P the r (G) ' With j u s t one exception, namely Kq, we determine R(G) f o r proper graphs u i t h a t

The longest cycle of a graph with a larg

The longest cycle of a graph with a large minimal degree

✍ Noga Alon 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 1 views

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamil