ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 31(2) (2011)
1Department of Computer Science and Systems Technology
University of Pannonia
H-8200 Veszprém, Egyetem u. 10, Hungary
2Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
3Department of Mathematics, Physics,
Computer Science and Geomatics
Troy University, Troy, AL 36082, USA
We consider hypergraphs H over a ``host graph'', that means a graph G
on the same vertex set X as H, such that each Ei induces a
connected subgraph in G. In the current setting we fix a graph or
multigraph G0, and assume that the host graph G is obtained by some
sequence of edge subdivisions, starting from G0.
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 |Ei| = 3 and 1 ≤ si ≤ 2 ≤ ti ≤ 3 holds for all i ≤ m.
We prove that for every fixed graph G0 and natural number r, colorability
is decidable in polynomial time over the class of r-uniform hypergraphs
(and more generally of hypergraphs with |Ei| ≤ r for all 1 ≤ i ≤ m)
having a host graph G obtained from G0 by edge subdivisions. Stronger
bounds are derived for hypergraphs for which G0 is a tree.
Keywords: mixed hypergraph, color-bounded hypergraph, vertex
coloring, arboreal hypergraph, hypertree, feasible set, host graph, edge
2010 Mathematics Subject Classification: 05C15, 05C65.
Received 23 November 2009
Revised 14 July 2010
Accepted 14 July 2010