Girth and Graph Coloring
For any positive integers g and χ, there exists a graph with girth at least g and chromatic number at least χ; for instance, the Grötzsch graph is triangle-free and has chromatic number 4, and repeating the Mycielskian construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number. Paul Erdős was the first to prove the general result, using the probabilistic method. More precisely, he showed that a random graph on n vertices, formed by choosing independently whether to include each edge with probability n(1 − g)/g, has, with probability tending to 1 as n goes to infinity, at most n/2 cycles of length g or less, but has no independent set of size n/2k. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than g, in which each color class of a coloring must be small and which therefore requires at least k colors in any coloring.
Read more about this topic: Girth (graph Theory)
Famous quotes containing the words girth and, girth and/or graph:
“It is said that when manners are licentious, a revolution is always near: the virtue of woman being the main girth and bandage of society; because a man will not lay up an estate for children any longer than whilst he believes them to be his own.”
—Ralph Waldo Emerson (1803–1882)
“It is said that when manners are licentious, a revolution is always near: the virtue of woman being the main girth and bandage of society; because a man will not lay up an estate for children any longer than whilst he believes them to be his own.”
—Ralph Waldo Emerson (1803–1882)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)