Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees |
| |
Authors: | Csilla Bujtá s |
| |
Affiliation: | a Department of Computer Science, University of Pannonia, H-8200 Veszprém, Egyetem u. 10, Hungary b Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary |
| |
Abstract: | A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E1,…,Em}, together with integers si and ti (1≤si≤ti≤|Ei|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge Ei satisfies si≤|φ(Ei)|≤ti, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge Ei induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (si,ti)=(2,|Ei|), while ‘C-edge’ assumes (si,ti)=(1,|Ei|−1)-the differences are rather significant. |
| |
Keywords: | Mixed hypergraph Vertex coloring Interval hypergraph Hypertree Circular hypergraph Chromatic spectrum Feasible set |
本文献已被 ScienceDirect 等数据库收录! |
|