Mixed hypercacti

KRÁĽ, Daniel; J KRATOCHVIL a HJ VOSS. Mixed hypercacti. Discrete Mathematics. AMSTERDAM: Elsevier B. V., 2004, roč. 286, 1-2, s. 99-113. ISSN 0012-365X. Dostupné z: https://doi.org/10.1016/j.disc.2003.11.051.

Základní údaje

Originální název

Mixed hypercacti

Autoři

KRÁĽ, Daniel; J KRATOCHVIL a HJ VOSS

Vydání

Discrete Mathematics, AMSTERDAM, Elsevier B. V. 2004, 0012-365X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.374

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.disc.2003.11.051

UT WoS

000223816400015

Klíčová slova anglicky

hypergraph coloring; mixed hypergraphs; hypertrees

---

Anotace

V originále

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.