CODEWITHSUNDEEP
algorithmmathgraph-theorydiscrete-mathematicsgraph-coloring
Sam
Sam

Reputation: 51

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 chromatic 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 chromatic number of any graph is at least equal to clique number

Clique Number: The size of the largest complete subgraph in a graph.

Chromatic Number: The minimum number of colors s.t. vertices can be colored with no adjacent vertices sharing a color.

Upvotes: 5

Views: 230

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59368

Given that a graph has no clique of size > q, here's how to color it with <= (q+n)/2 colors:

  1. If n <= q, just assign a new unique color to each vertex. This takes n colors, of course, which is <= (q+n)/2
  2. Otherwise, n>q and it is not a clique. Find any 2 vertices that are not connected, and give them the same unique color. Remove them from the graph and go back to step 1 to color the remainder;

Upvotes: 2

Related Questions