CS Paper Radar

A proof of Wang's planar $D$-coloring conjecture

Harshit Verma

cs.DM math.CO ·submitted 2026-10-23 21:49 UTC · v2
theory

Abstract

We prove Wang's planar $D$-coloring conjecture. A $D$-coloring of a graph is a proper edge coloring in which every subgraph isomorphic to $K_4$ minus an edge is rainbow. Wang conjectured that every planar graph of maximum degree $Δ$ has a $D$-coloring with $9$ colors if $Δ=4$, $10$ colors if $Δ=5$, and $2Δ-1$ colors if $Δ\ge6$. Hu, Kong and Wang proved the cases $Δ\le5$ and $Δ\ge33$. We prove the sharp bound $2Δ-1$ for every $Δ\ge6$, settling the remaining cases. The proof uses discharging; the case $Δ=6$ is computer-assisted.

Comment
22 pages, 3 figures. Ancillary files contain the certificates and verification scripts for the computer-assisted case of maximum degree 6

Closest papers

Nearest neighbours by meaning across the whole index.

Polychromatic 2-colorings with Bounded Discrepancy for Triangulations

cs.CG ·2026-09-25 ·Alma Arevalo Loyola, Ahmad Biniaz, Prosenjit Bose, Thomas Shermer
theory similarity 0.73
Abstract · 14 pages, 3 figures, SWAT 2026

A polychromatic $2$-coloring of a triangulation is a $2$-coloring of the vertices such that no face is monochromatic. The discrepancy of a coloring is the maximum difference between the sizes of the color classes. Asayama and Matsumoto (Graphs and Combinatorics, 2022) proved that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{5n-16}{9}$, and that there exists a class of triangulations for which every polychromatic $2$-coloring has discrepancy at least $\tfrac{n}{3} - 2$, where $n$ is the number of vertices. We improve the upper bound, showing that every triangulation admits a polychromatic $2$-coloring with discrepancy at most $\tfrac{3n-16}{7}$ and such a $2$-coloring can be computed in quadratic time. We also show a discrepancy of at most $n-\tfrac{4M}{3}$ for triangulations with a matching of size $M$. This implies, for example, that Delaunay triangulations admit a discrepancy of at most $\tfrac{n}{3}$. We provide a linear-time algorithm to compute a $2$-coloring whose discrepancy is at most $\tfrac{5n-24}{7}$. One of our results shows that any proper four coloring with the largest color class of size $\frac{n}{2}$ would imply a $2$-coloring with discrepancy at most $\frac{n}{3}$. The existence of such a proper coloring has been recently confirmed by Kawarabayashi, Yoneda, and Yoneda (arXiv 2026). Therefore the two results together confirm the discrepancy of at most $\frac{n}{3}$ for triangulations.

0.54

Large diameter for $(Δ+2)$-colouring reconfiguration

cs.DM math.CO ·2026-11-12 ·Wouter Cames van Batenburg
similarity 0.72
Abstract · 15 pages, 2 figures

Given a graph $G$ and an integer $k$, the reconfiguration graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\mathcal{R}_{Δ+2}(G)$ is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\mathcal{R}_{Δ+2}(G)$ is precisely equal to $n + μ$, for every graph $G$ with $n$ vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\frac{3}{2}μ-2$. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least $n+\frac{1}{2} μ$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

0.26

Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

cs.DM math.CO ·2026-10-19 ·Stefan Novaković, Duško Jojić
theory similarity 0.72
Abstract · 10 pages, 2 figures

We study the bipanchromatic number $χ_B$, introduced by Lalou et al. (Discrete Appl. Math. 391 (2026), 511-522) as the maximum number of colors in a panchromatic hypergraph coloring where every color appears at least twice. They show that merging uniquely occurring colors in a maximum panchromatic coloring gives the lower bound $β=χ_P-\lceilα/2\rceil \leq χ_B$, where $χ_P$ is the panchromatic number and $α$ is the minimum number of such colors among maximum panchromatic colorings. They conjectured that $χ_B=β$ and subsequently disproved it (arXiv:2610.08042). We identify the smallest counterexample, with six vertices and three hyperedges, both minimum possible. We show that the ratio bound $χ_B/β<2$ is asymptotically sharp and prove minimality results for the order and hyperedge count. For $3\leα<χ_P$ we show that every integer from $β$ to $χ_P-1$ occurs as $χ_B$ while $χ_P$ and $α$ are held fixed. Furthermore, we discover that the values $|V|,χ_P,α$ directly decide whether the conjectured equality holds except when $α=4$, where a matching reduction resolves the ambiguity. We derive the optimal universal lower bound $L$ depending only on $|V|,χ_P,α$ in the nontrivial regime $0<2α<|V|$. Finally, we prove $χ_B/L\le5/4$ and $χ_B/L\le6/5+1/(5L)$, with $5/4$ sharp and $6/5$ asymptotically sharp as $L\to\infty$.

0.11

Erdős-Gyárfás Balanced Five-Colorings

cs.DM math.CO ·2026-10-17 ·Hai Xia, Stefan Szeider
theory similarity 0.71
Abstract

A coloring of the edges of a complete graph with $r$ colors is balanced if the edges among any $r+1$ vertices use all $r$ colors. Erdős and Gyárfás (1999) conjectured that for all $r\ge3$ the complete graph $K_{r^2+1}$ has no balanced $r$-coloring. They proved the conjecture for $r=3$ and $r=4$. We prove the conjecture for $r=5$, the first new case settled in over two decades. There is no balanced $5$-coloring of $K_{26}$, and since $K_{25}$ has one, $K_{25}$ is the largest complete graph admitting a balanced $5$-coloring. We design a reduce--dispatch--enumerate workflow, where every machine step produces an artifact that can be independently checked. First, we use a machine-checked (Lean 4) proof to reduce the conjecture to a single extremal statement about the color class with the fewest edges: no graph on $26$ vertices has between $55$ and $65$ edges while every $6$ of its vertices span between $1$ and $11$ edges. We then search on the sparse class instead of its dense complement, which makes enumeration up to isomorphism feasible. With classical stability theorems for $K_6$-free graphs, we dispatch the five near-extremal edge counts analytically. For the exhaustive enumeration on the remaining six edge counts, we design efficient encodings with SAT modulo symmetries and parallel cube-and-conquer. We also certify all eleven edge counts: each of the $12{,}296$ subproblems carries a clausal refutation checked by the independent verifier drat-trim, and all $273{,}503{,}938$ symmetry-breaking clauses are also validated against the vertex permutations that justify them.

0.21

Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable

cs.DM math.CO ·2026-09-04 ·Matheus Adauto, Celina de Figueiredo, Diana Sasaki, Rafael Schneider
similarity 0.70
Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

0.20

A proof of a conjecture on bipartite correspondence packing

cs.DM math.CO ·2026-11-16 ·Xin Zhang
theory similarity 0.70
Abstract

A correspondence cover assigns a set of possible colors to each vertex of a graph. For each edge, a matching between the two endpoint color sets specifies the forbidden color pairs. A correspondence coloring selects one color at each vertex so that no forbidden pair is selected. A full correspondence packing is a collection of such colorings that uses every color at each vertex exactly once. We prove a conjecture of Cambie, Cames van Batenburg, Davies, and Kang [Random Structures & Algorithms 64 (2024), 62--93]. For every sufficiently large $D$, there is a positive integer $k(D)=(1+o(1))D/\log D$ such that every correspondence cover of any finite bipartite graph has a full correspondence packing if each color has at most $D$ forbidden partners and each vertex has $k(D)$ colors. More precisely, we prove this conclusion with \[ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil \] for every integer $D\ge\lceil e^{20}\rceil$.

0.21

Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound

cs.DM math.CO ·2026-09-27 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Sangita Saha, Saumya Sen
theory similarity 0.70
Abstract · 14 pages, 2 figures

A strong edge colouring of a graph $G$ is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $χ'_s(G)$. If each edge $e$ is assigned a list $L'(e)$ and its colour must belong to $L'(e)$, the corresponding parameter is the strong list chromatic index $χ'_{s,\ell}(G)$. From the definitions, $χ'_s(G)\leχ'_{s,\ell}(G)$. Barrett et al. gave an $8$-approximation for strong edge colouring on unit disk graphs and Grelier et al. improved the approximation factor to $6$. Our first result extends this factor-$6$ guarantee from unit disk graphs to the strictly larger class of disk graphs. In another direction, Erdős and Nešetřil conjectured that the strong chromatic index of a graph of maximum degree $Δ$ is asymptotically at most $1.25Δ^2$. The best published general asymptotic upper bound has leading coefficient $1.772$, due to Hurley et al. For unit disk graphs, Dębski et al. proved that $χ'_s(G) \leq 1.625 Δ^2$. Our second result improves this leading coefficient to $225/142 \approx 1.5845$. In fact, the proof establishes a stronger bound $χ'_{s,\ell}(G)\le\frac{225}{142} Δ^2+O(Δ)$ for unit disk graphs.

0.22

Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness

cs.DM math.CO ·2026-11-02 ·Kamal Santra
theory similarity 0.70
Abstract

A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound $ω(G)\leq\pcf(G)\leqω(G)+1$ and give an $O(n^2)$ construction from a partition tree. Every assignment of lists of at least $ω(G)+1$ colors also admits a PCF coloring that respects the lists. Deciding whether $ω(G)$ colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size $ω(G)+1$ always suffice, improving the previous ordinary-coloring bound of $ω(G)+2$. We use matchings to characterize when $ω(G)$ colors suffice and give an endpoint algorithm taking $2^{O(ω(G)^2)}n^{O(1)}$ time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking $O(n^{33})$ time. For bipartite permutation graphs, a smaller dynamic program gives an exact $O(n^{17})$ algorithm. Finally, if a bipartite graph is convex over an ordered shore $X$, we prove the sharp bound $\pcf(G)\leq\lceil\log_2(|X|+1)\rceil+3$ and construct a coloring in linear time from the order.

0.36