Cubic graph

A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings.

For example, the cubic graphs with 2g-2 vertices describe the different ways of cutting a surface of genus g ≥ 2 into pairs of pants.

Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit.

When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely.

Petersen's theorem states that every cubic bridgeless graph has a perfect matching.

[14] Lovász and Plummer conjectured that every cubic bridgeless graph has an exponential number of perfect matchings.

The conjecture was recently proved, showing that every cubic bridgeless graph with n vertices has at least 2n/3656 perfect matchings.

[15] Several researchers have studied the complexity of exponential time algorithms restricted to cubic graphs.

For instance, by applying dynamic programming to a path decomposition of the graph, Fomin and Høie showed how to find their maximum independent sets in time 2n/6 + o(n).

[13] The travelling salesman problem in cubic graphs can be solved in time O(1.2312n) and polynomial space.

[19] The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152.