pith. sign in

arxiv: 2310.04265 · v2 · pith:USZEWWFPnew · submitted 2023-10-06 · 🧮 math.CO · cs.DM

Clique number of tournaments

classification 🧮 math.CO cs.DM
keywords tournamentsboundedclassnumberpreccliquebackedgegraph
0
0 comments X
read the original abstract

Given a digraph $D$ together with an ordering $\prec$ of its vertices, the \emph{backedge graph} of $D$ with respect to $\prec$ is the undirected graph $D^{\prec}$ with the same vertex set as $D$, where $xy \in E(D^{\prec})$ if $xy \in A(D)$ and $y \prec x$. We introduce the notion of the \emph{clique number of a digraph} $D$, defined as the minimum clique number over all backedge graphs of $D$. We investigate its relationship with the dichromatic number. In particular, this concept allows us to define $\dic$-bounded classes of digraphs, which constitute the main topic of this paper, with a primary focus on tournaments. A class of tournaments is $\dic$-bounded if, for every tournament in the class, its dichromatic number is bounded by a function of its clique number. We study for which tournaments $H$ the class of $H$-free tournaments is $\dic$-bounded, and prove in particular that $H$ must have a backedge graph that is a forest. We prove that if a class of tournaments is $\dic$-bounded, then so is its closure under substitution. We also explore the relationship between $\dic$-bounded classes of tournaments and certain conjectures on tournaments. We prove that a $\dic$-bounded class of tournaments satisfies the $BIG \Rightarrow BIG$ Conjecture, and that a polynomially $\dic$-bounded class of tournaments satisfies the (tournament) Erd\H{o}s-Hajnal Conjecture.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Computing the degreewidth of a digraph is hard

    math.CO 2024-07 unverdicted novelty 8.0

    Proves NP-hardness of determining if an oriented graph has degreewidth at most 1, settling the last open case for oriented graphs.

  2. Decomposing tournaments into comparability graphs

    math.CO 2026-06 unverdicted novelty 7.0

    Defines pod(D) as the minimum partial-order arc cover size and proves dic(D) ≤ diomega(D)^pod(D) for digraphs, yielding polynomial dic-bounds for bounded-pod classes and resolving a conjecture on directed cliques in t...