Hypergraphs with Pendant Paths are not Chromatically Unique

• Autorzy: Ioan Tomescu
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

sunflower hypergraph; chromatic polynomial; chromatic unique- ness; pendant path

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 23-29

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Ioan Tomescu

• Faculty of Mathematics and Computer Science University of Bucharest Str. Academiei, 14 010014 Bucharest, Romania

Bibliografia

• [1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).
• [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]
• [3] M. Borowiecki and E. Lazuka, Chromatic polynomials of hypergraphs, Discuss.Math. Graph Theory 20 (2000) 293-301. doi:10.7151/dmgt.1128[Crossref]
• [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] 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] K. Dohmen, Chromatische Polynome von Graphen und Hypergraphen (Dissertation, D¨usseldorf, 1993).
• [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]
• [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] 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]
• [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] I. Tomescu, Sunflower hypergraphs are chromatically unique, Discrete Math. 285 (2004) 355-357. doi:10.1016/j.disc.2004.02.015[Crossref]
• [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] 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]
• [14] M.Walter, Some results on chromatic polynomials of hypergraphs, Electron. J. Com- bin. 16 (2009) R94.

Identyfikatory

DOI

10.7151/dmgt.1699