2011/12/14 by Yair Caro, Caro, Yair, Adriana Hansberg +1
Computer Science · Mathematics · #05C55 #05C65 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C55 #msc:05C65
paper · pdf · doi:10.48550/arxiv.1112.3302
24 pages
arxiv created 2011/12/14 · openalex publication_date 2011/12/14 · arxiv updated 2011/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The family D(k,m) of graphs having an orientation such that for every vertex v ∈ V(G) either (outdegree) °+(v) ≤ k or (indegree) °-(v) ≤ m have been investigated recently in several papers because of the role D(k,m) plays in the efforts to estimate the maximum directed cut in digraphs and the minimum cover of digraphs by directed cuts. Results concerning the chromatic number of graphs in the family D(k,m) have been obtained via the notion of d-degeneracy of graphs. In this paper we consider a far reaching generalization of the family D(k,m), in a complementary form, into the context of r-uniform hypergraphs, using a generalization of Hakimi's theorem to r-uniform hypergraphs and by showing some tight connections with the well known Ramsey numbers for hypergraphs.