On Reed's Conjecture in Triangle-Free Graphs
2010
The problem of finding the chromatic number of a graph G, i.e. the minimum number of colors needed to assign distinct colors to adjacent nodes of G, is NP-complete. However, there are some known bounds including the trivial lower bound χ(G) ≥ ω(G) and the upper bound provided by Brooks [2] χ(G) ≤ ∆(G) + 1, where χ(G) denotes the chromatic number, ∆(G) the maximum degree and ω(G) the number of nodes of a largest clique in G. In [6], Reed conjectured that
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
3
References
0
Citations
NaN
KQI