Hypergraphs with Pendant Paths are not Chromatically Unique

Ioan Tomescu

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 1, page 23-29
  • ISSN: 2083-5892

Abstract

top
In this note it is shown that every hypergraph containing a pendant path of length at least 2 is not chromatically unique. The same conclusion holds for h-uniform r-quasi linear 3-cycle if r ≥ 2.

How to cite

top

Ioan Tomescu. "Hypergraphs with Pendant Paths are not Chromatically Unique." Discussiones Mathematicae Graph Theory 34.1 (2014): 23-29. <http://eudml.org/doc/267927>.

@article{IoanTomescu2014,
abstract = {In this note it is shown that every hypergraph containing a pendant path of length at least 2 is not chromatically unique. The same conclusion holds for h-uniform r-quasi linear 3-cycle if r ≥ 2.},
author = {Ioan Tomescu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {sunflower hypergraph; chromatic polynomial; chromatic unique- ness; pendant path; chromatic uniqueness},
language = {eng},
number = {1},
pages = {23-29},
title = {Hypergraphs with Pendant Paths are not Chromatically Unique},
url = {http://eudml.org/doc/267927},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Ioan Tomescu
TI - Hypergraphs with Pendant Paths are not Chromatically Unique
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 23
EP - 29
AB - In this note it is shown that every hypergraph containing a pendant path of length at least 2 is not chromatically unique. The same conclusion holds for h-uniform r-quasi linear 3-cycle if r ≥ 2.
LA - eng
KW - sunflower hypergraph; chromatic polynomial; chromatic unique- ness; pendant path; chromatic uniqueness
UR - http://eudml.org/doc/267927
ER -

References

top
  1. [1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973). 
  2. [2] S.A. Bokhary, I. Tomescu and A.A. Bhatti, On the chromaticity of multi-bridge hypergraphs, Graphs Combin. 25 (2009) 145-152. doi:10.1007/s00373-008-0831-7[Crossref] Zbl1213.05065
  3. [3] M. Borowiecki and E. Lazuka, Chromatic polynomials of hypergraphs, Discuss.Math. Graph Theory 20 (2000) 293-301. doi:10.7151/dmgt.1128[Crossref] Zbl0979.05044
  4. [4] C.Y. Chao and E.G.Whitehead, Jr., On chromatic equivalence of graphs, in: Theory and Applications of Graphs, Y. Alavi and D.R. Lick (Ed(s)), (Lecture Notes Math. 642, New York, Springer (1978)) 121-131. 
  5. [5] D. Dellamonica, V. Koubek, D.M. Martin and V. R¨odl, On a conjecture of Thomassen concerning subgraphs of large girth, J. Graph Theory 67 (2011) 316-331. doi:10.1002/jgt.20534[Crossref] 
  6. [6] K. Dohmen, Chromatische Polynome von Graphen und Hypergraphen (Dissertation, D¨usseldorf, 1993). 
  7. [7] P. Erdős and R. Rado, Intersection theorems for systems of sets, J. Lond. Math. Soc. 35 (1960) 85-90. doi:10.1112/jlms/s1-35.1.85[Crossref] Zbl0103.27901
  8. [8] Z. Füredi, On finite set-systems whose intersection is a kernel of a star , Discrete Math. 47 (1983) 129-132. doi:10.1016/0012-365X(83)90081-X[Crossref] 
  9. [9] K.M. Koh and K.L. Teo, The search for chromatically unique graphs, Graphs Com- bin. 6 (1990) 259-285. doi:10.1007/BF01787578[Crossref] Zbl0727.05023
  10. [10] I. Tomescu, Chromatic coefficients of linear uniform hypergraphs, J. Combin. Theory (B) 72 (1998) 229-235. doi:10.1006/jctb.1997.1811[WoS][Crossref] 
  11. [11] I. Tomescu, Sunflower hypergraphs are chromatically unique, Discrete Math. 285 (2004) 355-357. doi:10.1016/j.disc.2004.02.015[Crossref] Zbl1047.05020
  12. [12] I. Tomescu, On the chromaticity of sunflower hypergraphs SH(n, p, h), Discrete Math. 307 (2007) 781-786. doi:10.1016/j.disc.2006.07.026[Crossref][WoS] 
  13. [13] I. Tomescu and S. Javed, On the chromaticity of quasi linear hypergraphs, Graphs Combin. 29 (2013) 1921-1026. doi:10.1007/s00373-012-1232-5[Crossref] Zbl1296.05080
  14. [14] M.Walter, Some results on chromatic polynomials of hypergraphs, Electron. J. Com- bin. 16 (2009) R94. Zbl1186.05059

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.