Jump to content

Szekeres snark

From Wikipedia, the free encyclopedia
Szekeres snark
The Szekeres snark
Named afterGeorge Szekeres
Vertices50
Edges75
Radius6
Diameter7
Girth5
Automorphisms20
Chromatic number3
Chromatic index4
Book thickness3
Queue number2
PropertiesSnark
Hypohamiltonian
Table of graphs and parameters

In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges.[1] It was the fifth known snark, discovered by George Szekeres in 1973.[2]

As a snark, the Szekeres graph is a connected, bridgeless cubic graph with chromatic index equal to 4. The Szekeres snark is non-planar and non-hamiltonian but is hypohamiltonian.[3] It has book thickness 3 and queue number 2.[4]

Another well known snark on 50 vertices is the Watkins snark discovered by John J. Watkins in 1989.[5]

[edit]

References

[edit]
  1. ^ Weisstein, Eric W. "Szekeres Snark". MathWorld.
  2. ^ Szekeres, G. (1973). "Polyhedral decompositions of cubic graphs". Bull. Austral. Math. Soc. 8 (3): 367–387. doi:10.1017/S0004972700042660.
  3. ^ Weisstein, Eric W. "Hypohamiltonian Graph". MathWorld.
  4. ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  5. ^ Watkins, J. J. "Snarks." Ann. New York Acad. Sci. 576, 606-622, 1989.