Content deleted Content added
Vince Vatter (talk | contribs) m →Two examples due to Erdős: The fourth edition of the Alon–Spencer textbook on the subject does not have Erdős' picture on the cover to highlight the method's association with him. |
→Second example: Fixed size of ceiling symbol |
||
Line 78:
For sufficiently large {{mvar|n}}, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).
Here comes the trick: since {{mvar|G}} has these two properties, we can remove at most {{math|''n''/2}} vertices from {{mvar|G}} to obtain a new graph {{math|''G′''}} on <math>n'\geq n/2</math> vertices that contains only cycles of length at least {{mvar|g}}. We can see that this new graph has no independent set of size <math>\left \lceil \frac{n'}{k}
This result gives a hint as to why the computation of the [[Graph coloring|chromatic number]] of a graph is so difficult: even when there are no local reasons (such as small cycles) for a graph to require many colors the chromatic number can still be arbitrarily large.
| |||