5
$\begingroup$

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the graph?

Is there anything more stronger known along these lines?

$\endgroup$
1

2 Answers 2

5
$\begingroup$

Since the vertices in a clique are pairwise adjacent, the vertices in the clique must be assigned distinct colors. Thus, any proper coloring of the graph will require at least as many colors as the size of the largest clique in the graph.

The difference between the chromatic number and its lower bound (the clique number) can be made arbitrarily large - the Mycielskian gives an explicit construction.

$\endgroup$
1
$\begingroup$

The answer to your first question is yes. A graph is perfect if the chromatic number of each induced subgraph is eqaul to the size of the largest cliqu in the subgraph. There is a large literature on these but, unfortunately, most graphs are not perfect

On the other hand there are triangle-free graphs with arbitrarily large chromatic number, so nothing much can said in general.

$\endgroup$
4
  • $\begingroup$ Thanks! Can you kindly explain the intuition behind behind being triangle free? $\endgroup$
    – user6818
    Sep 30, 2014 at 2:57
  • $\begingroup$ @user6818: I do not understand what you are asking. $\endgroup$ Sep 30, 2014 at 21:10
  • $\begingroup$ May be you can give the example you have in mind about triangle free graph with arbitrarily large chromatic number. $\endgroup$
    – user6818
    Oct 2, 2014 at 1:41
  • $\begingroup$ Takes the Kneser graph with vertices the subsets of size $k$ from a set of size $3k-1$, where two subsets are adjacency if they are disjoint. This has chromatic number $k+1$, by a a theorem due to Lovasz. $\endgroup$ Oct 2, 2014 at 2:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .