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:
“So the Snark found the verdict, although as it owned,
It was spent with the toils of the day:
When it said the word ‘GUILTY!’ the Jury all groaned,
And some of them fainted away.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)