***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Tinaz Ekim (Boğaziçi U.)

Thursday 29th March, 3:00 in Fine Hall 224.

Title: Edge-extremal graphs under degree and matching number restrictions.

We determine the maximum number of edges that a claw-free graph can have,
when its maximum degree and matching number are bounded. This is a famous 
problem that has been studied on general graphs, and for which there is a 
tight bound. The graphs achieving this bound contain in most cases an 
induced copy of a claw, which motivates studying the question on claw-free 
graphs. Note that on general graphs, if one of the mentioned parameters is 
not bounded, then there is no upper bound on the number of edges. We show 
that on claw-free graphs, bounding the matching number is sufficient for
obtaining an upper bound on the number of edges. The same is not true for
the degree, as a long path is claw-free. We give exact tight formulas for 
both when only the matching number is bounded and when both parameters are 
bounded. We also construct claw-free graphs whose edge numbers match the 
given bounds.  We conclude with several open questions that could be 
interesting to investigate further.

Joint with Cemil Dibek and Pinar Heggernes.

		---------------------------------------------

Next week: Jaehoon Kim

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)