We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pole F and one copy of C, where F is obtained from the Petersen graph by deleting the endpoints of one edge. We give direct SAT formulations for Petersen colorings and normal 5-edge-colorings. CaDiCaL 3.0.1 returned UNSAT for both formulas, and drat-trim verified the resulting DRAT proofs. The ancillary archive contains the construction, an explicit relabeling, the encoders, certificates, hashes, and verification programs. Combined with a theorem of Ma, Mattiolo, Steffen, and Wolf, the counterexample also implies that infinitely many connected simple bridgeless cubic graphs have no Petersen coloring. We also give a separately verified, nonisomorphic $D_3$-symmetric 112-vertex counterexample. We do not address whether 112 is minimum.
In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E(G) \to E(P)$ mapping any two adjacent edges of $G$ to two adjacent edges of the Petersen graph $P$. A positive resolution to Jaeger's conjecture would have immediately resolved several other famous and long-s...
J. Goedgebeur, Jorik Jooken, Edita Máčajová et al.· 0 citations
The claw-free Schur-positivity conjecture, recorded by Stanley (1998) and credited there to Gasharov, asserts that the chromatic symmetric function of every claw-free graph is Schur-positive. We give a counterexample on 12 vertices: the line graph $G$ of the graph obtained from a 4-cycle by attaching triangles at two o...
A proper conflict-free coloring is a proper vertex coloring in which every nonisolated vertex has a color occurring uniquely in its open neighborhood. We prove that every graph with neither a $K_5$-minor nor a $Q_6$-minor admits such a coloring with at most seven colors, where $Q_6=K_3\vee\overline{K_3}$. In particular...
A. Jiménez, C. Lintzmayer, M. Sambinelli· 1 citation
Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that for every connected graph G, the line graph of G has at most one more positive than negative adjacency eigenvalue; equivalently, the signature of a connected line graph is at most 1. We refute the conjecture with two independen...
We prove the 3-Decomposition Conjecture: every finite connected cubic loopless multigraph decomposes into a spanning tree, a 2-regular subgraph, and a matching. The proof rests on a new theorem on matching complements in subcubic graphs. Let H be a finite connected bridgeless simple graph of maximum degree three, and l...
The cycle double cover conjecture of Szekeres and Seymour, the proof of which was recently announced by OpenAI, states that every bridgeless graph has a collection of cycles covering every edge exactly twice. We study the counting version of this statement for cubic graphs, where we count circuit double covers --- coll...
Radek Husek, Robert Sámal· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
