Snark (graph Theory)
In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. (By Vizing's theorem, the chromatic index of a cubic graph is 3 or 4.) In order to avoid trivial cases, snarks are often restricted to have girth at least 5.
Writing in The Electronic Journal of Combinatorics, Miroslav Chladný states that
| “ | In the study of various important and difficult problems in graph theory (such as the Cycle double cover conjecture and the 5-Flow Conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown. | ” |
Read more about Snark (graph Theory): History, Properties, Snark Theorem, List of Snarks
Famous quotes containing the word snark:
“But oh, beamish nephew, beware of the day,
If your Snark be a Boojum! for then
You will softly and suddenly vanish away,
And never be met with again!”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)