Domination in transitive colorings of tournaments

DOI10.1016/J.JCTB.2014.02.001zbMATH Open1298.05132arXiv1302.4677OpenAlexW2072025981MaRDI QIDQ403357FDOQ403357

Dömötör Pálvölgyi, András Gyárfás

Publication date: 29 August 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: An edge coloring of a tournament $T$ with colors $1,2,dots,k$ is called it $k$-transitive m if the digraph $T(i)$ defined by the edges of color $i$ is transitively oriented for each $1leilek$. 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 ErdH 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(2^{2^{d-1}}dlogd)$ 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 $3^{14}$ to 64 and propose possible further improvements through finding the maximum domination number over parity tournaments.

Full work available at URL: https://arxiv.org/abs/1302.4677

zbMATH Keywords

dominationtransitive tournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On monochromatic paths in edge-coloured digraphs
• Almost tight bounds for \(\epsilon\)-nets
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• On monochromatic paths in m-coloured tournaments
• Covering with Euclidean boxes
• Dominating sets in \(k\)-majority tournaments.
• Monochromatic paths and at most 2-coloured arc sets in edge-coloured tournaments
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Monochromatic sinks in nearly transitive arc-colored tournaments
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• A lower bound on the size of an absorbing set in an arc-coloured tournament
• A proof of the Erdös-Sands-Sauer-Woodrow conjecture
• Domination and fractional domination in digraphs
• TRAVERSING A GRAPH IN GENERAL POSITION
• Domination in Digraphs
• Infinite quasi-transitive digraphs with domination number 2
• Domination in tournaments

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On dominator colorings in graphs 👍 👎
• Dominated colorings of graphs 👍 👎
• Total dominator colorings and total domination in graphs 👍 👎
• On some domination colorings of graphs 👍 👎
• On chromatic transversal domination in graphs 👍 👎
• Dominator and Total Dominator Colorings in Graphs 👍 👎
• Domination in colored complete graphs 👍 👎

This page was built for publication: Domination in transitive colorings of tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403357)