Sufficient and necessary condition for the chromatic equivalence of a class of graphs
-
摘要: 给出了两个伴随最小实根不小于\,$-$4\,的图伴随等价的一个充分必要条件. 据此, 也给出了这些图的补图色等价的一个充分必要条件.Abstract: A necessary and sufficient condition for the adjoint equivalence of two graphs with the adjoint minimum real root at least $-$4 was given. Based on this result, a necessary and sufficient condition of the chromatic equivalence for the complement graphs of these graphs can be naturally obtained.
-
Key words:
- chromatic polynomial /
- adjoint polynomial /
- chromatic equivalence /
- adjoint equivalence
-
[1] {1}CHIA G F. On the chromatic equivalence class of graphs[J]. DiscreteMath, 1998, 178: 15-23.{2}DOFG F M, TEO K L, LITTLE C H C, et al. Chromaticity of somefamilies of dense graphs[J]. Discrete Math, 2002, 258: 303-321.{3}LIU R Y. A new method to find chromatic polynomial of graph and itsapplications[J]. Kexue Tongbao, 1987, 32: 1508-1509 (In Chinese,English summary).{4}KORFHAGE R R. $\sigma$-polynomials and graph coloring[J]. J CombinTheory Ser B, 1978, 24: 137-153.{5}DONG F M, KOH K M, TEO K L. Chromatic Polynomials and Chromaticityof Graphs[M]. Singapore: World Scientific Publishing, 2005.{6}ZHAO H X, LI X L, ZHANG S G, et al. On the minimum real root of thepolynomial and chromatic uniqueness of graphs[J]. Discrete Math,2004, 281: 271-294.{7}MA H C, REN H Z. The chromatic equivalence classes of thecomplements of graphs with the minimum real roots of their adjointpolynomials greater than $-4$[J]. Discrete Math, 2008, 308:1830-1836.{8}LIU R Y. Adjoint polynomials and chromatically unique graphs[J].Discrete Math, 1997, 172: 85-92.
点击查看大图
计量
- 文章访问数: 7984
- HTML全文浏览量: 24
- PDF下载量: 2286
- 被引次数: 0