Show that chromatic number of any graph G is less or equal to the sum of number of vertices and clique number of graph, and divided by two
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.