Domination in transitive colorings of tournaments

DOI10.1016/J.JCTB.2014.02.001MaRDI QIDQ403357zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• Chromatic transversal domination in graphs
• On chromatic transversal domination in graphs
• Total dominator colorings and total domination in graphs
• Dominator and total dominator colorings in graphs
• Domination in colored complete graphs
• On some domination colorings of graphs
• On dominator colorings in graphs
• Dominated colorings of graphs
• scientific article; zbMATH DE number 2170484
• Coloring and domination in graphs

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 970814 (Why is no real title available?)
• Almost tight bounds for \(\epsilon\)-nets
• Covering with Euclidean boxes
• Dominating sets in \(k\)-majority tournaments.
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Kernels by monochromatic directed paths in 3-colored tournaments and quasi-tournaments
• Monochromatic paths and at most 2-coloured arc sets in edge-coloured tournaments
• Monochromatic sinks in nearly transitive arc-colored tournaments
• On monochromatic paths in edge-coloured digraphs
• On monochromatic paths in m-coloured tournaments
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(10)

• Infinite quasi-transitive digraphs with domination number 2
• Transitive edge coloring of graphs and dimension of lattices
• Domination in tournaments
• TRAVERSING A GRAPH IN GENERAL POSITION
• A proof of the Erdös-Sands-Sauer-Woodrow conjecture
• Domination in 3-tournaments
• A lower bound on the size of an absorbing set in an arc-coloured tournament
• Covering 2‐colored complete digraphs by monochromatic d $d$‐dominating digraphs
• Domination and fractional domination in digraphs
• Domination in digraphs

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)