Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: edge subdivision

Sortuj według:

Ogranicz wyniki do:

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

Color-bounded hypergraphs, V: host graphs and subdivisions

100%

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

1 Discussiones Mathematicae Graph Theory

1 Bujtás C.

1 Tuza Z.

1 Voloshin V.

1 2011

Wyniki wyszukiwania

Color-bounded hypergraphs, V: host graphs and subdivisions