Let’s denote chromtic number of graph G as k, clique number of graph G (so the size of the largest complete subgraph in graph G) as q, and n as number of vertices of G, I have a problem with showing that k<=(n+q)/2.
So what I know about any graph G is, that cromatic number of any graph is at least equal to clique number
New contributor
Sam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.