Re: cromatic number

On Apr 13, 6:20 am, mdifrancesco2...@xxxxxxxxx wrote:
Is always true that cromatic number is equal to the max cardinality of
a clique? Can you give me the proof please.
Thank you.

No, it is very untrue. There is a theorem by Erdos that says: "For
every k and l there exists a graph G with chromatic number >= k and
girth >= l".
In particular, for every k there exists a triangle-free graph with
chromatic number k (see Mycielski graphs for an explicit
construction). Note that a triangle-free graph has a maximum clique of
size 2 (just an edge).
Pick any chromatic number you want, and you can (explicitly) construct
a graph with that chromatic number that does not have a clique with
size greater than 2.

.

Relevant Pages

  • Re: small combination problem
    ... I wanted to get a nice graph at the end, even though I missed and edge. ... > Leaving behind the clique that you found. ... It performs the 'intersection' of the ranges. ... second' numbers in the solutions the MOP ...
    (comp.programming)
  • Re: small combination problem
    ... I wanted to get a nice graph at the end, even though I missed and edge. ... > Leaving behind the clique that you found. ... It performs the 'intersection' of the ranges. ... second' numbers in the solutions the MOP ...
    (comp.theory)
  • Re: Time complexity of couting the number of cliques on k nodes
    ... of vertices of the host graph is part of the input. ... especially as the clique size k gets ... Remove all vertices of degree less than k-1 and their neighboring ... take the resulting subgraph and go to step ...
    (sci.math)
  • Re: small combination problem
    ... Now 0 is only used twice, so remove the solutions containing 0. ... Leaving behind the clique that you found. ... The graph for this case is: ... into maximal stable sets, there exists some clique which hits every ...
    (comp.theory)
  • Re: small combination problem
    ... Now 0 is only used twice, so remove the solutions containing 0. ... Leaving behind the clique that you found. ... The graph for this case is: ... into maximal stable sets, there exists some clique which hits every ...
    (comp.programming)