Color-bounded hypergraphs, V: host graphs and subdivisions

Csilla Bujtás; Zsolt Tuza; Vitaly Voloshin

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 223-238
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Csilla Bujtás, Zsolt Tuza, and Vitaly Voloshin. "Color-bounded hypergraphs, V: host graphs and subdivisions." Discussiones Mathematicae Graph Theory 31.2 (2011): 223-238. <http://eudml.org/doc/270851>.

@article{CsillaBujtás2011,
abstract = {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.},
author = {Csilla Bujtás, Zsolt Tuza, Vitaly Voloshin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {mixed hypergraph; color-bounded hypergraph; vertex coloring; arboreal hypergraph; hypertree; feasible set; host graph; edge subdivision},
language = {eng},
number = {2},
pages = {223-238},
title = {Color-bounded hypergraphs, V: host graphs and subdivisions},
url = {http://eudml.org/doc/270851},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Csilla Bujtás
AU - Zsolt Tuza
AU - Vitaly Voloshin
TI - Color-bounded hypergraphs, V: host graphs and subdivisions
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 223
EP - 238
AB - 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.
LA - eng
KW - mixed hypergraph; color-bounded hypergraph; vertex coloring; arboreal hypergraph; hypertree; feasible set; host graph; edge subdivision
UR - http://eudml.org/doc/270851
ER -

References

top
  1. [1] Cs. Bujtás and Zs. Tuza, Mixed colorings of hypergraphs, Electronic Notes in Discrete Math. 24 (2006) 273-275, doi: 10.1016/j.endm.2006.06.026. 
  2. [2] Cs. Bujtás and Zs. Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs and Combinatorics 24 (2008) 1-12, doi: 10.1007/s00373-007-0765-5. 
  3. [3] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309 (2009) 4890-4902, doi: 10.1016/j.disc.2008.04.019. Zbl1210.05088
  4. [4] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Math. 309 (2009) 6391-6401, doi: 10.1016/j.disc.2008.10.023. Zbl1225.05189
  5. [5] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, III: Model comparison, Appl. Anal. and Discrete Math. 1 (2007) 36-55. 
  6. [6] Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, IV: Stable colorings of hypertrees, Discrete Math. 310 (2010) 1463-1474, doi: 10.1016/j.disc.2009.07.014. Zbl1219.05055
  7. [7] Cs. Bujtás and Zs. Tuza, Coloring intervals with four types of constraints, in: 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, A. Frank et al., Eds. (Budapest, Hungary, May 16-19, 2009) 393-401. 
  8. [8] E. Drgas-Burchardt and E. Łazuka, On chromatic polynomials of hypergraphs, Appl. Math. Letters 20 (2007) 1250-1254, doi: 10.1016/j.aml.2007.02.006. Zbl1137.05030
  9. [9] T. Jiang, D. Mubayi, Zs. Tuza, V.I. Voloshin and D. West, The chromatic spectrum of mixed hypergraphs, Graphs and Combinatorics 18 (2002) 309-318, doi: 10.1007/s003730200023. Zbl0994.05063
  10. [10] D. Král', J. Kratochví l, A. Proskurowski and H.-J. Voss, Coloring mixed hypertrees, in: 26th Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1928 (Springer-Verlag, 2000) 279-289. 
  11. [11] D. Král, J. Kratochvíl, and H.-J. Voss, Mixed hypercacti, Discrete Math. 286 (2004) 99-113, doi: 10.1016/j.disc.2003.11.051. Zbl1064.05060
  12. [12] Zs. Tuza and V. Voloshin, Uncolorable mixed hypergraphs, Discrete Appl. Math. 99 (2000) 209-227, doi: 10.1016/S0166-218X(99)00134-1. Zbl0943.05035
  13. [13] Zs. Tuza and V. Voloshin, Problems and results on colorings of mixed hypergraphs, Horizon of Combinatorics (E. Gyori et al., Eds.), Bolyai Society Mathematical Studies 17 (Springer-Verlag, 2008) 235-255. Zbl1201.05040
  14. [14] V. Voloshin, The mixed hypergraphs, Computer Science Journal of Moldova 1 (1993) 45-52. 
  15. [15] V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Combin. 11 (1995) 25-45. Zbl0827.05027
  16. [16] V.I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monographs 17 Amer. Math. Soc., 2002. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.