The Petersen coloring conjecture of Jaeger asserts that every bridgeless cubic graph admits a Petersen coloring. Recently, Putman presented an explicit counterexample on $112$ vertices and verified its non-colorability by showing, using a SAT solver, that an instance with $3640$ variables and $68324$ clauses is unsatisfiable. We give a short human-checkable proof that this graph is indeed a counterexample. Our proof determines the coloring behavior of the multipoles used in the construction by means of small explicit finite case analyses and reduces the final contradiction to a simple structural property of the line graph of the Petersen graph. Besides providing a proof that does not rely on a large SAT computation, our approach gives further insight into the gadgets underlying the construction.
In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematica...
W. Cames van Batenburg, J. Goedgebeur, Jorik Jooken· 0 citations
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-pol...
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the neg...
For every odd integer $t\ge17$, we prove that an explicit circulant graph on $5t-10$ vertices is doubly saturated $R(3,t)$-good. The graph is triangle-free and has independence number $t-1$. Adding any nonedge creates a triangle, whereas deleting any edge creates an independent set of order $t$. This settles Conjecture...
Abhishek Saigal, Akaash R. Parthasarathy· 0 citations
A famous conjecture of Erd\H{o}s and Hajnal (1969) states that for every integer $g\ge 4$ there is a smallest function $f_g:\mathbb{N}\to\mathbb{N}$ such that every graph of chromatic number at least $f_g(k)$ contains a subgraph of chromatic number $k$ and girth at least $g$. So far, this has only been proved for $g=4$...
Raphael Steiner· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
