Domination in transitive colorings of tournaments

Pálvölgyi, Dömötör and Gyárfás, András (2014) Domination in transitive colorings of tournaments. JOURNAL OF COMBINATORIAL THEORY SERIES B (107). pp. 1-11. ISSN 0095-8956

Preview

Text transcikkvegleges.pdf Download (299kB) | Preview

Abstract

An edge coloring of a tournament T with colors 1,2,…,k is called \it k-transitive \rm if the digraph T(i) defined by the edges of color i is transitively oriented for each 1≤i≤k. We explore a conjecture of the second author: For each positive integer k there exists a (least) p(k) such that every k-transitive tournament has a dominating set of at most p(k) vertices. We show how this conjecture relates to other conjectures and results. For example, it is a special case of a well-known conjecture of Erd\H os, Sands, Sauer and Woodrow (so the conjecture is interesting even if false). We show that the conjecture implies a stronger conjecture, a possible extension of a result of B\'ar\'any and Lehel on covering point sets by boxes. The principle used leads also to an upper bound O(22d−1dlogd) on the d-dimensional box-cover number that is better than all previous bounds, in a sense close to best possible. We also improve the best bound known in 3-dimensions from 314 to 64 and propose possible further improvements through finding the maximum domination number over parity tournaments.

Actions (login required)

Edit Item