← All problems

Petersen coloring conjecture

41 years old · traced to

Let PP denote the Petersen graph, i.e. the graph whose vertex set is the collection of all 22-element subsets of {1,2,3,4,5}\{1,2,3,4,5\}, two such subsets being joined by an edge if and only if they are disjoint; PP has 1010 vertices and 1515 edges.

For a finite graph GG (multiple edges and loops permitted), call a set C⊆E(G)C \subseteq E(G) a cycle of GG if every vertex of GG is incident with an even number of edges of CC (loops counted twice); equivalently, the cycles of GG are exactly the elements of the cycle space of GG over GF(2)\mathrm{GF}(2), i.e. the edge sets of the Eulerian subgraphs of GG.

Given graphs GG and HH, a map f:E(G)→E(H)f : E(G) \to E(H) is cycle-continuous if for every cycle CC of HH the preimage

f−1(C)={e∈E(G):f(e)∈C}f^{-1}(C) = \{ e \in E(G) : f(e) \in C \}

is a cycle of GG.

Then: for every finite bridgeless graph GG there exists a cycle-continuous map f:E(G)→E(P)f : E(G) \to E(P).

Equivalent formulations
  1. In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

    source: Wikipedia

References
  1. Wikipedia, Petersen graph, the article this problem comes from.

Source: Wikipedia

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.