Fix a positive integer $r$, and a graph $G$ that is $K_{3,r}$-minor-free. Let $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a ``token'' on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated ``token jumping'', removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ into $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono (2014) to be fixed-parameter tractable. That is, the problem can be solved in time $f(k)\cdot Poly(n)$, for some function $f$ and polynomial $Poly(n)$, where $n$ denotes the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a $K_{3,r}$-minor-free graph (for some fixed positive integer $r$) into an equivalent problem on a ($K_{3,r}$-minor-free) graph with order $O(k)$. This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz (2024) and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille (2026). For planar graphs, we further strengthen this upper bound to get a kernel of size at most $39k$.

Abstract. A proper coloring of a graph is conflict-free if, for every nonisolated vertex, some color is used exactly once on its neighborhood. Caro, Petruševski, and Škrekovski [ Discrete Math., 346 (2023), 113221] proved that every graph [Formula: see text] has a proper conflict-free coloring with at most [Formula: see text] colors and conjectured that [Formula: see text] colors suffice for every connected graph [Formula: see text] with [Formula: see text]. Our first main result is that even for list-coloring, [Formula: see text] colors suffice for every graph [Formula: see text] with [Formula: see text]; we also prove slightly weaker bounds for all graphs with [Formula: see text]. These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph [Formula: see text] and a “conflict” hypergraph [Formula: see text]. As another corollary of our results in this general framework, every graph has a proper [Formula: see text]-list-coloring such that every bichromatic component is a path on at most three vertices, where the number of colors is optimal up to a constant factor. Our proof uses a fairly new type of recursive counting argument called Rosenfeld counting, which is a variant of the Lovász local lemma or entropy compression. We also prove an asymptotically optimal result for a fractional analogue of our general framework for proper conflict-free coloring for pairs of a graph and a conflict hypergraph. A corollary states that every graph [Formula: see text] has a fractional [Formula: see text]-coloring such that every fractionally bichromatic component has at most two vertices. In particular, it implies that the fractional analogue of the conjecture of Caro, Petruševski, and Škrekovski holds asymptotically in a strong sense.

For each integer $k\ge 2$, we determine a sharp bound on ${mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most $k$ vertices. For each $k$ we construct an infinite family of examples showing our result is the best possible. Our results imply that every planar graph $G$ of girth at least 9 (resp., 8, 7) has a partition of $V(G)$ into an independent set $I$ and a set $F$ such that $G[F]$ is a forest with each component of order at most 3 (resp., 4, 6). Hendrey, Norin, and Wood asked for the largest function $g(a,b)$ such that if ${mad}(G)

For integers $a\ge 2b>0$, a circular $a/b$-flow is a flow that takes values from $\{\pm b, \pm(b+1), \dots, \pm(a-b)\}$. The Planar Circular Flow Conjecture states that every $2k$-edge-connected planar graph admits a circular $(2+\frac{2}{k})$-flow. The cases $k=1$ and $k=2$ are equivalent to the Four Color Theorem and Grötzsch's 3-Color Theorem. For $k\ge 3$, the conjecture remains open. Here we make progress when $k=4$ and $k=6$. We prove that (i) every 10-edge-connected planar graph admits a circular $5/2$-flow and (ii) every 16-edge-connected planar graph admits a circular 7/3-flow. The dual version of statement (i) on circular coloring was previously proved by Dvořák and Postle [ Combinatorica, 37 (2017), pp. 863--886], but our proof has the advantages of being much shorter and avoiding the use of computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because the counterexamples to Jaeger's original Circular Flow Conjecture are 12-edge-connected nonplanar graphs that admit no circular 7/3-flow. Thus, the planarity hypothesis of (ii) is essential.

A multigraph $G$ is near-bipartite if $V(G)$ can be partitioned as $I,F$ such that $I$ is an independent set and $F$ induces a forest. We prove that a multigraph $G$ is near-bipartite when $3|W|-2|E(G[W])|\ge -1$ for every $W\subseteq V(G)$, and $G$ contains no $K_4$ and no Moser spindle. We prove that a simple graph $G$ is near-bipartite when $8|W|-5|E(G[W])|\ge -4$ for every $W\subseteq V(G)$, and $G$ contains no subgraph from some finite family $\mathcal{H}$. We also construct infinite families to show that both results are the best possible in a very sharp sense.

An acyclic edge-coloring of a graph $G$ is a proper edge-coloring of $G$ such that the subgraph induced by any two color classes is acyclic. The acyclic chromatic index, $\chi'_a(G)$, is the smallest number of colors allowing an acyclic edge-coloring of $G$. Clearly $\chi'_a(G)\ge \Delta(G)$ for every graph $G$. Cohen, Havet, and Müller conjectured that there exists a constant $M$ such that every planar graph with $\Delta(G)\ge M$ has $\chi'_a(G)=\Delta(G)$. We prove this conjecture.

A simple graph $G$ is overfull if ${|E(G)|}>\Delta\lfloor|V(G)|/2\rfloor$. By the pigeonhole principle, every overfull graph $G$ has $\chi'(G)>\Delta$. The core of a graph, denoted $G_\Delta$, is the subgraph induced by its vertices of degree $\Delta$. Vizing's adjacency lemma implies that if $\chi'(G)>\Delta$, then $G_\Delta$ contains cycles. Hilton and Zhao conjectured that if $G$ is connected with $\Delta\ge 4$ and $G_\Delta$ has maximum degree 2, then $\chi'(G)>\Delta$ precisely when $G$ is overfull. We prove this conjecture for the case $\Delta=4$.

Let $\chi_{\ell}$ and $\chi_{OL}$ denote the list-chromatic number and online list-chromatic number. We prove that if $G$ is a quasi-line graph with maximum degree greater than clique number, i.e., $\Delta(G)>\omega(G)$, and $\Delta(G)\ge 69$, then its online list-chromatic number is less than its maximum degree, i.e., $\chi_{OL}(G)\le \Delta(G)-1$. Together with our previous work, this implies that if $G$ is a claw-free graph with $\Delta(G)>\omega(G)$ and $\Delta(G)\ge 69$, then its list-chromatic number is less than its maximum degree, i.e., $\chi_{\ell}(G)\le \Delta(G)-1$. This verifies the list-coloring analogue of a conjecture of Borodin and Kostochka for every claw-free graph $G$ with $\Delta(G)\ge 69$.

In 2011, the second author conjectured that every line graph $G$ satisfies $\chi(G)\leq\max\big\{\omega(G),\frac{5\Delta(G)+8}{6}\big\}$. This conjecture is best possible as shown by replacing each edge in a 5-cycle by $k$ parallel edges and taking the line graph. In this paper we prove the conjecture. We also develop more general techniques and results that will likely be of independent interest, due to their use in attacking the Goldberg--Seymour Conjecture.

Brooks' theorem implies that if a graph has $\Delta\ge 3$ and $\chi > \Delta$, then $\omega=\Delta+1$. Borodin and Kostochka conjectured that if $\Delta\ge 9$ and $\chi\ge \Delta$, then $\omega\ge \Delta$. We show that if $\Delta\ge 13$ and $\chi\ge \Delta$, then $\omega \ge \Delta-3$. For a graph $G$, let ${\mathcal{H}(G)}$ denote the subgraph of $G$ induced by vertices of degree $\Delta$. We also show that if $\chi\ge \Delta$, then $\omega\ge \Delta$ or $\omega({\mathcal{H}(G)})\ge \Delta-5$.

We prove that every claw-free graph $G$ that does not contain a clique on $\Delta(G) \geq 9$ vertices can be $\Delta(G) - 1$ colored.

A graph is $(7,2)$-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose 2 colors for each edge from its list so that no color is chosen for two incident edges. We show that every 3-edge-colorable graph is $(7,2)$-edge-choosable and also that many non-3-edge-colorable 3-regular graphs are $(7,2)$-edge-choosable.