2017/07/28 by Joergen Bang-Jensen, Bang-Jensen, Joergen, Stéphane Bessy +5 · 1 citation
Computer Science · Mathematics · #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1707.09349
openalex publication_date 2017/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let k be a fixed integer. We determine the complexity of finding a p-partition (V1, …, Vp) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by Vi, (1≤ i≤ p) is at least k smaller than the maximum out-degree of D. We show that this problem is polynomial-time solvable when p≥ 2k and \cal NP-complete otherwise. The result for k=1 and p=2 answers a question posed in \citebangTCS636. We also determine, for all fixed non-negative integers k1,k2,p, the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition (V1,V2) such that the digraph induced by Vi has maximum out-degree at most ki for i∈ [2]. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition (V1,V2) such that each vertex v∈ Vi has at least as many neighbours in the set V3-i as in Vi, for i=1,2 is \cal NP-complete. This solves a problem from \citekreutzerEJC24 on majority colourings.