• DocumentCode
    3026518
  • Title

    Ohba´s Conjecture is True for Graphs K_6,3*t,2*(k-2t-4),1*(t+3)

  • Author

    Zheng, Guoping ; Tang, Qing ; Shen, Yufa ; Guo, Jun ; Cui, Yu

  • Author_Institution
    Dept. of Math., Hebei Normal Univ. of Sci. & Technol., Qinhuangdao, China
  • fYear
    2010
  • fDate
    23-24 Oct. 2010
  • Firstpage
    63
  • Lastpage
    66
  • Abstract
    A graph G is called chromatic-choosable if ch(G)=χ(G). Ohba´s conjecture states that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. In this paper we show that Ohba´s conjecture is true for complete multipartite graphs K6,3*t,2*(k-2t-4),1*(t+3) and its all k-chromatic sub graphs for all integers t≥0 and k≥2t+4, that is, ch(K6,3*t,2*(k-2t-4),1*(t+3))=k, which extends the result ch(K6,3*t,2*(k-6),1*4)=k given by Shen et al. [J. of Mathematical Research and Exposition, 27(2)(2007) 264-272].
  • Keywords
    graph theory; Ohba conjecture; chromatic-choosable; complete multipartite graphs; k-chromatic sub graphs; Color; Cryptography; Graph theory; Helium; Image color analysis; Presses; Chromatic-choosable graphs; Complete multipartite graphs; List coloring; Ohba´s conjecture; f - choosable;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Cryptography and Network Security, Data Mining and Knowledge Discovery, E-Commerce & Its Applications and Embedded Systems (CDEE), 2010 First ACIS International Symposium on
  • Conference_Location
    Qinhuangdao
  • Print_ISBN
    978-1-4244-9595-5
  • Type

    conf

  • DOI
    10.1109/CDEE.2010.22
  • Filename
    5759370