A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers and satisfying for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge satisfies . The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which and holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.