Abstract. For an integer [Formula: see text] and a graph [Formula: see text], let [Formula: see text] be the graph that has vertex set all proper [Formula: see text]-colorings of [Formula: see text], and an edge between two vertices [Formula: see text] and [Formula: see text] whenever the coloring [Formula: see text] can be obtained from [Formula: see text] by a single Kempe change. A theorem of Meyniel from 1978 states that [Formula: see text] is connected with diameter [Formula: see text] for every planar graph [Formula: see text]. We significantly strengthen this result by showing that there is a positive constant [Formula: see text] such that [Formula: see text] has diameter [Formula: see text] for every planar graph [Formula: see text].

Abstract. A circular [Formula: see text]-coloring of a signed graph [Formula: see text] is an assignment [Formula: see text] of points of a circle [Formula: see text] of circumference [Formula: see text] to the vertices of [Formula: see text] such that for each positive edge [Formula: see text] of [Formula: see text] the distance of [Formula: see text] from [Formula: see text] is at least 1 and for each negative edge [Formula: see text] the distance of [Formula: see text] from the antipode of [Formula: see text] is at least 1. The circular chromatic number of [Formula: see text], denoted [Formula: see text], is the infimum of [Formula: see text] such that [Formula: see text] admits a circular [Formula: see text]-coloring. This notion was recently defined by Naserasr, Wang, and Zhu, who, among other results, proved that for any signed [Formula: see text]-degenerate simple graph [Formula: see text] we have [Formula: see text]. For [Formula: see text], examples of signed [Formula: see text]-degenerate simple graphs of circular chromatic number [Formula: see text] are provided. But for [Formula: see text] only examples of signed 2-degenerate simple graphs of circular chromatic number arbitrarily close to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If [Formula: see text] is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then [Formula: see text]. Motivated by this observation, we provide an improved upper bound of [Formula: see text] for the circular chromatic number of a signed 2-degenerate simple graph on [Formula: see text] vertices and an improved upper bound of [Formula: see text] for the circular chromatic number of a signed bipartite planar simple graph on [Formula: see text] vertices. We then show that each of the bounds is tight for any value of [Formula: see text].

Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be Hamiltonian. This is a special case of a conjecture of Barnette and Goodey, stating that 3-connected planar cubic graphs with faces of size at most 6 are Hamiltonian. We prove Barnette and Goodey's conjecture.

We show that every (sub)cubic [Formula: see text]-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least [Formula: see text]. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.

Reed conjectured that for every $\varepsilon>0$ and every integer $\Delta$, there exists g such that the fractional total chromatic number of every graph with maximum degree $\Delta$ and girth at least g is at most $\Delta+1+\varepsilon$. The conjecture was proven to be true when $\Delta=3$ or $\Delta$ is even. We settle the conjecture by proving it for the remaining cases.