Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    Almost every complement of a tadpole graph is not chromatically unique

    Access Status
    Fulltext not available
    Authors
    Wang, J.
    Huang, J.
    Teo, Kok Lay
    Belardo, F.
    Liu, R.
    Ye, C.
    Date
    2013
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Wang, J. and Huang, J. and Teo, K.L. and Belardo, F. and Liu, R. and Ye, C. 2013. Almost every complement of a tadpole graph is not chromatically unique. Ars Combinatoria. 108: pp. 33-49.
    Source Title
    Ars Combinatoria
    ISSN
    0381-7032
    School
    School of Electrical Engineering, Computing and Mathematical Science (EECMS)
    URI
    http://hdl.handle.net/20.500.11937/63383
    Collection
    • Curtin Research Publications
    Abstract

    The study of chromatically unique graphs has been drawing much attention and many results are surveyed in [4, 12, 13]. The notion of adjoint polynomials of graphs was first introduced and applied to the study of the chromaticity of the complements of the graphs by Liu [17] (see also [4]). Two invariants for adjoint equivalent graphs that have been employed successfully to determine chromatic unique graphs were introduced by Liu [17] and Dong et al. [4] respectively. In the paper, we shall utilize, among other things, these two invariants to investigate the chromaticity of the complement of the tadpole graphs C n (P m ), the graph obtained from a path P m and a cycle C n by identifying a pendant vertex of the path with a vertex of the cycle. Let G stand for the complement of a graph G. We prove the following results: The graph C n-1 (P 2 ) is chromatically unique if and only if n = 5, 7. Almost every C n (P m ) is not chromatically unique, where n = 4 and m = 2. AMS classification: 05C15, 05C60. Copyright © 2013, Charles Babbage Research Centre.

    Related items

    Showing items related by title, author, creator and subject.

    • The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph
      Achuthan, Nirmala; Achuthan, Narasimaha; Simanihuruk, M. (2011)
      A graph is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number Xk(G) ...
    • Relational evidence theory and spatial interpretation procedures.
      Pearce, Adrian (1996)
      Spatial interpretation involves the intelligent processing of images for learning, planning and visualisation. This involves building systems which learn to recognise patterns from the content of unconstrained data such ...
    • Evaluation of anthropometry activities for high school science: student outcomes and classroom environment
      Lightburn, Millard E. (2002)
      The study involved the evaluation of anthropometric activities for high school science. The activities actively engaged students in the process of gathering, processing and analyzing data derived from human body measurements, ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.