##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Wayne Goddard

#### Clemson University

## Binding Number, Cycles and Cliques

##### Abstract:

In 1973 Woodall defined the binding number of a graph and showed that a binding number of $3/2$ implies that the graph has a hamiltonian cycle. He conjectured that the same threshold implies that the graph has a triangle, and moreover, cycles of all lengths. This was later proven by Shi Ronghua. In 1974 Andr\'{a}sfai, Erd\H{o}s and S\'{o}s showed that a $K_r$-free graph with large enough minimum degree is $(r-1)$-colorable. Several authors investigated further results about homomorphisms and colorings of dense graphs with low clique number. In this talk we revisit the connections among binding number, cycles and cliques in graphs. This includes joint work with Jeremy Lyle.

Host: Jacques Verstraete

### March 18, 2008

### 4:00 PM

### AP&M 7321

****************************