← All problems

Petersen graph vertex-irreducibility conjecture

16 years old · documented by

A bridgeless cubic class 2 graph GG is vertex-irreducible if, for any two vertices x,y∈V(G)x,y\in V(G), the graph G−{x,y}G-\{x,y\} cannot be extended to a bridgeless cubic class 2 graph by adding edges.

Petersen graph vertex-irreducibility conjecture. The Petersen graph is the only vertex-irreducible bridgeless cubic class 2 graph.

A vertex-irreducible cubic graph is known to be cyclically 5-edge-connected, and the conjecture was verified computationally for all cubic bridgeless graphs with at most 36 vertices. The general statement remains open in the source.

References

3 papers in this index state this conjecture (2009–2017). The statement above is taken from the most recent of them; the others are arXiv:1504.03500, arXiv:0901.0759.

Source: M. A. Fiol, G. Mazzuoccolo and E. Steffen, “On measures of edge-uncolorability of cubic graphs: A brief survey and some new results”, arXiv:1702.07156 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.