Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: mixed hypergraph

Sortuj według:

Ogranicz wyniki do:

Chromatic Polynomials of Mixed Hypercycles

100%

Allagan J. A., Slutzky D.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 3

547-558

We color the vertices of each of the edges of a C-hypergraph (or cohypergraph) in such a way that at least two vertices receive the same color and in every proper coloring of a B-hypergraph (or bihypergraph), we forbid the cases when the vertices of any of its edges are colored with the same color (monochromatic) or when they are all colored with distinct colors (rainbow). In this paper, we determined explicit formulae for the chromatic polynomials of C-hypercycles and B-hypercycles

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Color-bounded hypergraphs, V: host graphs and subdivisions

63%

Bujtás C., Tuza Z., Voloshin V.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 2

223-238

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set 𝓔 = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀. 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 $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Allagan J. A.

1 Bujtás C.

1 Slutzky D.

1 Tuza Z.

1 Voloshin V.

1 2014

1 2011

Wyniki wyszukiwania

Chromatic Polynomials of Mixed Hypercycles

Color-bounded hypergraphs, V: host graphs and subdivisions