chromatic number of a graph versus its complementWhat can be said about the rate of growth of f(n), defined by f ( n ) = min | V ( G ) | = n [ χ ( G ) + χ ( G ¯ ) ] ,where the minimum is taken over all graphs G on n vertices.Two observations.(1) Either G or G ¯ contains a clique on roughly logn vertices by Ramsey theory, so f ( n ) ≥ c 1 log ⁡ n for some constant c 1 &gt; 0.(2) If G=G(n,1/2) is a random graph, then χ ( G ) ≈ χ ( G ¯ ) ≈ n / log ⁡ n n/ log n almost surely, so we also have f ( n ) ≤ c 2 n / log ⁡ n n/log n for some constant c 2 &gt; 0.These bounds seem hopelessly far apart.Can we improve on the bounds c 1 log ⁡ n ≤ f ( n ) ≤ c 2 n / log ⁡ nfor all sufficiently large n?

Question

chromatic number of a graph versus its complementWhat can be said about the rate of growth of f(n), defined by  f  (  n  )  =      min                  |            V      (      G      )              |            =      n            [    χ    (    G    )    +    χ    (                  G        ¯              )    ]    ,where the minimum is taken over all graphs G on n vertices.Two observations.(1) Either G or             G      ¯       contains a clique on roughly logn vertices by Ramsey theory, so   f  (  n  )  ≥      c    1    log  ⁡  n  for some constant       c    1    &amp;gt;  0.(2) If G=G(n,1/2) is a random graph, then   χ  (  G  )  ≈  χ  (            G      ¯        )  ≈  n      /    log  ⁡      n    n/ log n almost surely, so we also have   f  (  n  )  ≤      c    2      n      /    log  ⁡  n n/log n for some constant       c    2    &amp;gt;  0.These bounds seem hopelessly far apart.Can we improve on the bounds      c    1    log  ⁡  n  ≤  f  (  n  )  ≤      c    2      n      /    log  ⁡  nfor all sufficiently large n?

frisiao · Accepted Answer

(Answering for posterity, don&#039;t select this as best.)First, extend @ccc&#039;s proof to show that if   p  q  ≥  n then   f  (  n  )  ≤  p  +  q. You do this first by taking a graph on n nodes consisting of (at most) p cliques of at most q nodes each, and noting that   χ  (  G  )  ≤  p and   χ  (            G      ¯        )  ≤  qNow, as shown by ccc in coments above,  ⌈  2      n    ⌉  ≤  f  (  n  )  ≤  2  ⌈      n    ⌉This reduces to at most two values.In general, if   ⌈  2  x  ⌉  &amp;lt;  2  ⌈  x  ⌉, then the fractional part of x is in   (  0  ,      1    2    ). So we only need to consider the cases where the fractional part of       n   is in this range, that is,       n    =  p  +  δwhere p is an integer and   0  &amp;lt;  δ  &amp;lt;      1    2  .Claim:   p  (  p  +  1  )  ≥  n.We know that   p  (  p  +  1  )  ≥  n. Since n and p(p+1) are integers, this means   p  (  p  +  1  )  ≥  nTherefore,   f  (  n  )  ≤  2  p  +  1  =  ⌈  2      n    ⌉So we know that   f  (  n  ) is always   ⌈  2      n    ⌉

Marisol Rivers · Accepted Answer

Although there is already an accepted answer, I answer to give a bit more information, for what I have to say would not fit in a comment.This is the Nordhaus-Gaddum Theorem:If G is a graph of order n, then  2      n    ≤  χ  (  G  )  +  χ  (            G      ¯        )  ≤  n  +  1  n  ≤  χ  (  G  )  ⋅  χ  (            G      ¯        )  ≤            (                        n          +          1                2            )        2  And, there is no possible improvement of any of these bounds. In fact, much more can be said:Let n be a positive integer. For every two positive integers a and b such that  2      n    ≤  a  +  b  ≤  n  +  1  n  ≤  a  b  ≤            (                        n          +          1                2            )        2  there is a graph G of order n such that χ(G)=a and   p  q  ≥  n.Source: Graphs &amp;amp; Digraphs (Fifth edition) by Chartrand, Lesniak, and Zhang

What can be said about the rate of growth of f(n), defined by f(n)=min/(|V(G)|=n) [χ(G)+χ(bar G)], where the minimum is taken over all graphs G on n vertices.

Answered question

Answer & Explanation

New Questions in Descriptive Statistics