ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Improvement of the numerical condition of chromaticity on complete tripartite graphs

  • 1.

    Department of Basic Courses, Huainan Vocational and Technical College, Huainan 232001, China

  • 2.

    School of Mathematics, Hefei University of Technology, Hefei 230009, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2016.12.003
  • Received Date: 31 October 2015
  • Accepted Date: 20 February 2016
  • Rev Recd Date: 20 February 2016
  • Publish Date: 30 December 2016
    Abstract

  • Abstract

    Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ)=P(G, λ) implies G≌H. By comparing the number of the triangular subgraph and that of the quadrangular subgraph without chords, the chromatic uniqueness on the tripartite graph K(n-k,n-v,n) was discussed. It was proved that K(n-k,n-v,n) is chromatically unique for n≥v2(k-v/3)/4+v and k≥v≥2 and that K(n-k,n-2,n) is chromatically unique for n≥k+2,k≥2.

    Abstract

    Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ)=P(G, λ) implies G≌H. By comparing the number of the triangular subgraph and that of the quadrangular subgraph without chords, the chromatic uniqueness on the tripartite graph K(n-k,n-v,n) was discussed. It was proved that K(n-k,n-v,n) is chromatically unique for n≥v2(k-v/3)/4+v and k≥v≥2 and that K(n-k,n-2,n) is chromatically unique for n≥k+2,k≥2.
    • FullText(HTML)
  • loading
    • References(11)
  • [1]
    CHIA G L,GOH B H, KO H M. The chromaticity of some families of complete tripartite graphs[J]. Scientia, Series A, Mathematical Sciences, 1988, 2: 27-37.
    [2]
    LIU Ruyin, ZHAO Haixing, YE Chengfu. A complete solution to a conjecture on chromatic unique of complete tripartite graphs[J]. Dis Math, 2004,289: 175-179.
    [3]
    徐利民.完全t部图K(n-k,n,…,n)的色唯一性[J].中国科学技术大学学报,2008, 38(9): 1 036-1 041.
    XU Limin. Chromatic uniqueness of complete t-partite graphs K(n-k,n,…,n) [J]. Journal of University of Science and Technology of China, 2008, 38(9):1 036-1 041.
    [4]
    SU Keyi, CHEN Xiangen. A not on chromatic uniqueness of completely tripartite graphs[J]. Mathematical Research & Exposition,2010, 30(2): 233-240.
    [5]
    LAU G C, PENG Y H. Chromatic uniqueness of certain complete tripartite graphs[J]. Acta Mathematica Sinica, English Series, 2011, 27(5): 919-926.
    [6]
    CHEN X, SU K, YAO B, et al. A note on chromatic uniqueness of certain complete tripartite graphs[J].Ars Combinatoria, 2012, 105: 205-211.
    [7]
    徐利民,杨志林. 完全三部图K(n-k,n-v,n)的色唯一性[J]. 中国科学技术大学学报,2013,43(3): 190-196,201.
    XU Limin, YANG Zhilin. Chromatic uniqueness of complete tripartite graphs K(n-k,n-v,n)[J]. Journal of University of Science and Technology of China, 2013,43(3): 190-196,201.
    [8]
    KOH K M, TEO K L. The search for chromatically unique graphs[J].Graphs and Combinatorics, 1990, 6(3):259-285.
    [9]
    徐利民.完全三部图K(n-k,n,n) 的色唯一性[J].大学数学,2006,22(3):78-82.
    XU Limin. On the chromaticity of complete tripartite graphs K(n-k,n,n)[J]. College Mathematics, 2006, 22(3):78-82.
    [10]
    徐利民.特殊子图的计数[J].淮南职业技术学院学报,2011,11(3): 74-77.
    XU Limin. The enumeration of special subgraphs[J]. Journal of Huainan Vocational & Technical College, 2011, 11(3):74-77.
    [11]
    CHIA G L, HO C K. Chromatic uniqueness classes of complete tripartite graphs[J]. Discrete Math, 2009, 309(1):134-143.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    CHIA G L,GOH B H, KO H M. The chromaticity of some families of complete tripartite graphs[J]. Scientia, Series A, Mathematical Sciences, 1988, 2: 27-37.
    [2]
    LIU Ruyin, ZHAO Haixing, YE Chengfu. A complete solution to a conjecture on chromatic unique of complete tripartite graphs[J]. Dis Math, 2004,289: 175-179.
    [3]
    徐利民.完全t部图K(n-k,n,…,n)的色唯一性[J].中国科学技术大学学报,2008, 38(9): 1 036-1 041.
    XU Limin. Chromatic uniqueness of complete t-partite graphs K(n-k,n,…,n) [J]. Journal of University of Science and Technology of China, 2008, 38(9):1 036-1 041.
    [4]
    SU Keyi, CHEN Xiangen. A not on chromatic uniqueness of completely tripartite graphs[J]. Mathematical Research & Exposition,2010, 30(2): 233-240.
    [5]
    LAU G C, PENG Y H. Chromatic uniqueness of certain complete tripartite graphs[J]. Acta Mathematica Sinica, English Series, 2011, 27(5): 919-926.
    [6]
    CHEN X, SU K, YAO B, et al. A note on chromatic uniqueness of certain complete tripartite graphs[J].Ars Combinatoria, 2012, 105: 205-211.
    [7]
    徐利民,杨志林. 完全三部图K(n-k,n-v,n)的色唯一性[J]. 中国科学技术大学学报,2013,43(3): 190-196,201.
    XU Limin, YANG Zhilin. Chromatic uniqueness of complete tripartite graphs K(n-k,n-v,n)[J]. Journal of University of Science and Technology of China, 2013,43(3): 190-196,201.
    [8]
    KOH K M, TEO K L. The search for chromatically unique graphs[J].Graphs and Combinatorics, 1990, 6(3):259-285.
    [9]
    徐利民.完全三部图K(n-k,n,n) 的色唯一性[J].大学数学,2006,22(3):78-82.
    XU Limin. On the chromaticity of complete tripartite graphs K(n-k,n,n)[J]. College Mathematics, 2006, 22(3):78-82.
    [10]
    徐利民.特殊子图的计数[J].淮南职业技术学院学报,2011,11(3): 74-77.
    XU Limin. The enumeration of special subgraphs[J]. Journal of Huainan Vocational & Technical College, 2011, 11(3):74-77.
    [11]
    CHIA G L, HO C K. Chromatic uniqueness classes of complete tripartite graphs[J]. Discrete Math, 2009, 309(1):134-143.
    Recommended articles
    TrendMD
    Volume 46 Issue 12 page: 981-987
    Cover

    Article Metrics

    Article views (70) PDF downloads(209)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return