2023/07/12 by Kwon, O-joung, Lian, Xiaopan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.05897
In this paper, we consider a variant of dichromatic number on digraphs with prescribed sets of arcs. Let D be a digraph and let Z1, Z2 be two sets of arcs in D. For a subdigraph H of D, let A(H) denote the set of all arcs of H. Let μ(D, Z1, Z2) be the minimum number of parts in a vertex partition P of D such that for every X∈ P, the subdigraph of D induced by X contains no directed cycle C with |A(C)∩ Z1|≠ |A(C)∩ Z2|. For Z1=A(D) and Z2=∅, μ(D, Z1, Z2) is equal to the dichromatic number of D. We prove that for every digraph F and every tuple (ae,be,re, qe) of integers with qe≥ 2 and gcd(ae,qe)=gcd(be,qe)=1 for each arc e of F, there exists an integer N such that if μ(D, Z1, Z2)≥ N, then D contains a subdigraph isomorphic to a subdivision of F in which each arc e of F is subdivided into a directed path~Pe such that~ae|A(Pe)∩ Z1|+be|A(Pe)∩ Z2|≡ re\pmod qe. This generalizes a theorem of Steiner [Subdivisions with congruence constraints in digraphs of large chromatic number, arXiv:2208.06358] which corresponds to the case when (ae, be, Z1, Z2)=(1, 1, A(D), ∅).