CS Paper Radar

Biplanar graphs with independence number two are 9-colorable

Stefan Szeider

cs.LO math.CO ·submitted 2026-09-23 13:33 UTC · v1
theoryhot direction

Abstract

A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have chromatic number at least 10. Gethner and Sulanke asked in 2009 whether such a graph exists. We show that it does not, and more generally that every biplanar graph with independence number at most 2 is 9-colorable. The proof embeds a hypothetical counterexample in the union of two sphere triangulations, enumerates with SAT modulo symmetries the 3271 graphs that pass a necessary filter for the complement of such a union, and shows with a SAT solver that none of them is such a complement; a matching argument reduces the general statement to this computation and one further case on 18 vertices. The computational part of the proof, including the completeness of the enumeration and every refutation, is checked in Lean 4, assuming three classical facts about planar graphs. The Lean development, the SAT instances, and the enumeration certificates are available on Zenodo.

Closest papers

Nearest neighbours by meaning across the whole index.

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.73
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

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.69
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

Elementary graphs are chromatic-choosable

cs.DM math.CO ·2026-10-12 ·Narayanan N, Nandana K. Vasudevan, K. Somasundaram
theory similarity 0.67
Abstract · 13 page, 5 figures, 1 table

A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.

0.34

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.67
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

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.67
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15

Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number

cs.DM math.CO ·2026-10-29 ·Siddhesh Chaubal
similarity 0.67
Abstract · 8 pages, 3 figures. Submitted to Aequationes Mathematicae

A set $S$ of vertices of a graph $G$ is a mutual-visibility set if every pair of vertices of $S$ is joined by a shortest path whose internal vertices avoid $S$, and the mutual-visibility chromatic number $χ_μ(G)$ is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that $χ_μ(G)\leχ(G)$ whenever $G$ has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph $G_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.

0.56

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

cs.DM math.CO ·2026-10-23 ·Harshit Verma
theory similarity 0.66
Abstract · 22 pages, 3 figures. Ancillary files contain the certificates and verification scripts for the computer-assisted case of maximum degree 6

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.

0.10

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

cs.DM math.CO ·2026-10-17 ·Hai Xia, Stefan Szeider
theory similarity 0.66
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