Domination in transitive colorings of tournaments

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

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)

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

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

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• On monochromatic paths in m-coloured tournaments
• Covering with Euclidean boxes
• Title not available (Why is that?)
• Dominating sets in \(k\)-majority tournaments.
• Monochromatic paths and at most 2-coloured arc sets in edge-coloured tournaments
• Kernels by monochromatic directed paths in 3-colored tournaments and quasi-tournaments
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Monochromatic sinks in nearly transitive arc-colored tournaments

Cited In (10)

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

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)