SHANDONG SCIENCE ›› 2018, Vol. 31 ›› Issue (6): 100-102.doi: 10.3976/j.issn.1002-4026.2018.06.016

• Other Research Article • Previous Articles    

A conjecture about vertex coloring

ZHANG Xiang-bo   

  1. Linpan Middle School,Dezhou 251507, China
  • Received:2017-12-28 Published:2018-12-20 Online:2018-12-20

Abstract:

The conjecture of vertex coloring was proposed in this paper:χ(G)≤S+C, where  χ(G) is the vertex coloring number of agraph and S is vertex number of maximum clique;C is a constant and CZ+. If C=1,p is vertex number of G, we prove that for some graphs of S=p-6, χ(G)≤p-5.

Key words: maximum degree, vertex coloring, the maximum clique

CLC Number: 

  • O157.5

Open Access This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0), which permits third parties to freely share (i.e., copy and redistribute the material in any medium or format) and adapt (i.e., remix, transform, or build upon the material) the articles published in this journal, provided that appropriate credit is given, a link to the license is provided, and any changes made are indicated. The material may not be used for commercial purposes. For details of the CC BY-NC 4.0 license, please visit: https://creativecommons.org/licenses/by-nc/4.0