Uniform Mixed Hypergraphs: The Possible Numbers of Colors |
| |
Authors: | Email author" target="_blank">Csilla?BujtásEmail author Zsolt?Tuza |
| |
Institution: | (1) Department of Computer Science, University of Pannonia, Egyetem u. 10, H–8200 Veszprém, Hungary;(2) Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13–17, H–1111 Budapest, Hungary |
| |
Abstract: | For a mixed hypergraph
, where
and
are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every
meets some class in more than one vertex, and every
has a nonempty intersection with at least two classes. The feasible set of
, denoted
, is the set of integers k such that
admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either
or S is an ‘interval’
for some integer k ≥ 1.
In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all
and all
, r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either
for some natural number k ≥ r − 1, or S is of the form
where S′′ is any (possibly empty) subset of
and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets
can be obtained under the restriction
, i.e. within the class of ‘bi-hypergraphs’.
Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613. |
| |
Keywords: | Mixed hypergraph vertex coloring feasible set |
本文献已被 SpringerLink 等数据库收录! |
|