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:
“The indictment had never been clearly expressed,
And it seemed that the Snark had begun,
And had spoken three hours, before any one guessed
What the pig was supposed to have done.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)