University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Domination in structured tournaments

Domination in structured tournaments

Add to your list(s) Download to your calendar using vCal

  • UserNicolas Bousquet (CNRS, Grenoble)
  • ClockThursday 01 June 2017, 15:00-16:00
  • HouseLTC Watson.

If you have a question about this talk, please contact Guillem Perarnau.

There exists tournaments, such as random tournaments, for which the domination number is arbitrarily large. One can naturally ask what happens if we add some structure on the tournament, for instance if the tournament can be represented using a bounded number of partial orders. Alon et al. showed that k-majority tournaments have bounded domination number. Gyarfas and Palvolgyi conjectured that the following is true : If a tournament admits a partition of its arc set into k quasi orders, then its domination number is bounded in terms of k. We provide a short proof that the following more general conjecture due to Erdos, Sands, Sauer and Woodrow: If the arcs of a tournament T are colored with k colors, there is a set X of at most g(k) vertices such that for every vertex v of T, there is a monochromatic path from X to v.

(joint work with William Lochet and Stéphan Thomassé)

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.