Publication details
Mixed hypercacti
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.disc.2003.11.051 |
| Keywords | hypergraph coloring; mixed hypergraphs; hypertrees |
| Description | A mixed hypergraph H is a triple (V, C, D) where V is its vertex set and C and D are families of subsets of V (called C-edges and D-edges). A vertex coloring of H is proper if each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of H is the set of all k's such that there exists a proper coloring using exactly k colors. The feasible set is gap-free if it is an interval of integers. A graph is a strong/weak cactus if all its cycles are vertex/edge-disjoint. A hypergraph is spanned by a graph (with the same vertex set) if the edges of the hypergraph induce connected subgraphs. A strong/weak hypercactus is spanned by a strong/weak cactus. We prove that the feasible set of any mixed strong hypercactus is gap-free. We find infinitely many mixed weak hypercacti such that the feasible set of any of them contains a gap. For each connected non-planar graph G not equal K-5, we find a mixed hypergraph spanned by G whose feasible set contains a gap. (C) 2004 Elsevier B.V. All rights reserved. |