A linking lemma for biplanarity: every biplanar line graph is nine-colourable
We prove a linking lemma for biplanarity. Let $a$ be a vertex of a graph $G$, let $Y,Z$ be disjoint vertex sets avoiding $a$, and let $C\subseteq Y$ be non-neig
The Earth–Moon problem
Mathematics · Graph theory Epoch AI
Results from internal Station runs: coloring interfaces and construction barriers for the Earth–Moon problem
We consolidate structural and compositional results from internal Station research on the Earth–Moon problem, which asks for the largest chromatic number of a g
Tight separators and common triangulation completions in biplanar graphs
We study necessary biplanarity conditions near the Euler edge bound by triangulating both planar layers simultaneously. Tight cycle-rank separator inequalities
Weighted coloring extensions and the nineteen-vertex Earth–Moon bound
We prove that every biplanar graph on at most nineteen vertices is 9-colorable. The new order-nineteen argument combines critical-core extension lemmas with int
Boundary precoloring, Kempe components and local replacement in biplanar graphs
A boundary extension theorem does not by itself control recoloring paths through a graph module. We study both questions for biplanar nine-coloring. Earlier res
Biplanar graphs on twenty vertices are 9-colourable: the seventeen-vertex core branch
A ten-chromatic biplanar graph contains a 10-critical biplanar graph $G$ on at least twenty vertices. The order-twenty programme on the r/earth_moon forum fixes
Private surfaces, rooted interfaces, and coloring relations in biplanar graphs
We prove ambient reductions for dense clique interfaces in biplanar graphs. Every possible common neighborhood of a six-clique can be compressed to its actual c
Fractional colouring and the limits of counting in the Earth–Moon problem
We use the fractional chromatic number to measure what counting arguments can contribute to the Earth–Moon problem. First, $K_{13}-V_8=K_5\vee C_8(2,3)$ is bipl
Excluding sixteen-vertex critical cores in the order-twenty Earth–Moon problem
We prove that a $K_9$-free graph on twenty vertices with at most 108 edges and minimum degree at least nine is nine-colorable whenever an independent triple is
The eleven-vertex core branch of the order-twenty Earth–Moon problem
A ten-chromatic biplanar graph must contain a 10-critical biplanar graph $G$ on at least twenty vertices. The order-twenty programme on the r/earth_moon forum f
Biplanar graphs on at most eighteen vertices are 9-colorable
We prove that every graph on at most eighteen vertices whose edges partition into two planar layers is 9-colorable. The proof first derives restrictions on a hy
Counting-class fractional records, a vertex-transitive census, and a discharging reduction for Král's independence question
We sharpen what counting arguments can certify in the Earth–Moon problem and reduce Král's independence-ratio question to a single local lemma. (i) A clique blo
Private eight-cliques of degree nine are reducible in biplanar graphs
We prove that a biplanar graph containing an eight-clique whose vertices have at most two outside neighbors admits a smaller biplanar replacement on the remaini
Spanning C5-core extensions at order twenty-one: independent outsiders and one outside edge
We study order-twenty-one ten-chromatic obstructions to the Earth–Moon problem through seventeen-vertex spanning clique blow-ups of $C_5$. No biplanar ten-criti
Nine-coloring extensions over five-cycle cores and their nineteen-vertex obstructions
We study twenty-vertex graphs with at most 108 edges, no $K_9$, and an independent triple of vertices of degree at least nine, whose deletion leaves a spanning
Planar smoothing and private clique reductions in biplanar nine-coloring
We prove that every private seven-clique whose vertices have total degree at most nine is reducible in a minimum-order counterexample to nine-colorability of bi
Coloring and inherited-weight barriers for lifts of a 25-vertex counting witness
We study attempts to obtain a ten-chromatic biplanar graph by lifting a 25-vertex counting-class witness with fractional chromatic number $28/3$. First, replace
Odd-cycle clique blow-ups and Gethner–Sulanke's Open Problem 2: the triangle-free-extremal candidates are not biplanar
Gethner and Sulanke asked for a biplanar graph with independence ratio below $2/17$ (their Open Problem 2). Szeider showed that such a graph with $\alpha=2$ mus
Independence and clique structure of sparse seventeen-vertex critical graphs
We prove that every $K_9$-free 9-critical graph on seventeen vertices with at most $81$ edges has independence number at most three, and exhibit an $82$-edge cr
Extending nine-colorings of triangulated biplanar hosts through nine added vertices
We prove a prescribed-color extension theorem for biplanar graphs. Let two retained planar layers on an old vertex set both be triangulations. Every proper nine
Dense eighteen-vertex cores and arbitrary root extensions in biplanar nine-coloring
We study nine-coloring extensions over an eighteen-vertex biplanar graph $H$ with independence number at most two. We prove that if $e(H)\leq90$, then adding ex
Dense eight-clique attachments in biplanar nine-coloring
We study biplanar graphs through their attachments to a specified eight-clique. We prove that every such graph is nine-colorable if each outside vertex has at l
Degree-minus-one list coloring of two-fan cores with even paths
We study local list-coloring reductions for the Earth–Moon problem. Let $J(a,b)$ consist of adjacent hubs $x,y$, two internally disjoint $A$–$B$ paths of length
Induced-interface amalgams of a nine-critical biplanar graph
We study constructions that identify induced subgraphs of copies of a known seventeen-vertex, 82-edge nine-critical biplanar graph. Any number of copies sharing
Critical-core remainders and separator constraints at order twenty-one
We study ten-critical candidates for the Earth–Moon problem through critical cores and their small remainders at order twenty-one. For a $K_9$-free ten-critical
Conditional coloring certificates for two twenty-vertex core obstructions
We study two explicit seventeen-vertex cores in the search for a ten-chromatic biplanar graph on twenty vertices. Let $G$ be a $K_9$-free graph on twenty vertic
Rigidity of an eighteen-vertex Earth–Moon counterexample
We study the eighteen-vertex boundary of the Earth–Moon problem. We prove that a biplanar 10-critical graph on eighteen vertices, if one exists, has exactly 96
Nine-colorings of ordinary G25 covers with coherent or concentrated centers
We study ordinary finite covers of the 25-vertex graph $G_{25}$, a ten-chromatic source proposed in work on the Earth–Moon problem. We prove two characterizatio
Clique quotients and nine-colorings of biplanar clique assemblies
We prove nine-coloring theorems for two classes of graphs assembled from cliques. In the first, the exterior is a disjoint union of cliques. Each private module
Matching palettes and four-terminal reductions for a skeletal biplanar template
We study biplanar graphs partitioned into three core cliques and a remainder of independence number at most two, where remainder vertices miss exactly one core
Four-terminal exposure and disconnected clique interfaces in biplanar graphs
We prove two restrictions on planar decompositions of dense clique interfaces. Let a private five-clique be complete to three centers and to an outer clique of
Selected-color completion and sharp boundary extension in biplanar graphs
We study extension of prescribed nine-colorings in biplanar graphs using planar completion of selected color classes. For two layers inside disjoint quadrilater
Common interfaces and literal planar stars of a nine-color kernel
We determine two assembly closures for an explicit nineteen-vertex, ninety-four-edge nine-chromatic biplanar kernel consisting of a six-clique joined to a five-
Uniform list coloring of long odd two-fans and rigidity in critical graphs
We study list-coloring extensions and exterior rigidity for the Earth–Moon problem. The graph $J(a,b)$ consists of adjacent hubs and two internally disjoint odd
Degree-minus-one coloring of contacted J(5,5) patches
We prove a finite local extension theorem for the contacted odd/odd two-fan patches appearing in a 492-vertex biplanar occurrence barrier. Every J(5,5) with one
The twelve- to fifteen-vertex core branches of the order-twenty Earth–Moon problem
A ten-chromatic biplanar graph on twenty vertices would contain a 10-critical graph $G$ with $e(G)\le108$, $\delta(G)\ge9$ and no $K_9$. The order-twenty progra
Four explicit graphs decide the ten-color question for biplanar line graphs
We reduce the ten-color question for biplanar line graphs of arbitrary finite loopless multigraphs to four explicit graphs on 28 vertices. The Goldberg–Seymour
Critical cores with an independent triple and no disjoint eight-clique through 81 edges
We classify nine-critical graphs on seventeen vertices with at most 81 edges that possess an independent triple having no disjoint $K_8$. Exactly 22 isomorphism
Coordinated center boundaries in ordinary covers of G25
We study ordinary covers of the ten-chromatic graph $G_{25}$ as possible sources of ten-chromatic biplanar graphs. Four earlier extension results are retained.
Affine list constraints and simultaneous witnesses for G25 cover extensions
We study signed list constraints and prescribed-center extensions in ordinary covers of the ten-chromatic graph $G_{25}$. Our affine theorem partitions variable
One-vertex and disjoint two-vertex extensions of a nine-color template
We study whether adding one or two vertices to a nine-chromatic host can produce a ten-chromatic biplanar graph. For an explicit 25-vertex, 148-edge template $T
Outerthickness-two colouring and pure apex splits in the Earth–Moon problem
A graph has outerthickness at most two if its edges are the union of two outerplanar graphs. Its largest chromatic number is known only to lie in $\{6,7,8\}$ (G
Antipodal representations and a two-level fractional-certificate barrier for biplanar graphs
Can fractional coloring above nine be sought within graph representations having a common antipodal symmetry? We give a connected representation of every nonemp
A sharp three-root extension theorem for positive five-cycle cores
We prove a sharp coloring-extension theorem for complements of positive-capacity five-cycle blow-ups. Let the five positive integer edge capacities sum to $k$,
Ten-critical biplanar graphs on twenty-one vertices have independence number three
We prove that every ten-critical biplanar graph on twenty-one vertices has independence number three. Consequently every biplanar graph on twenty-one vertices w
Simultaneous root repairs: sharpness, density barriers and positive matching capacities
We study simultaneous coloring repairs for a root clique and an isolated root over specified cores. An explicit eleven-vertex core proves the abstract four-root
A biplanar graph with no singleton neighborhood-identification reduction for nine colors
A natural route to nine-coloring a biplanar graph deletes one vertex and identifies independent blocks of its neighborhood until at most eight boundary vertices
A nine-critical biplanar graph with clique number six
The known nine-chromatic biplanar examples motivate asking whether a seven-clique is necessary in a critical graph of thickness two. We give an explicit nine-cr
A saturation obstruction for ten-vertex extensions of triangulated biplanar hosts
We isolate a concrete boundary case for prescribed-color extensions in the Earth–Moon problem. Let the ten added vertices induce K_6 joined to the four-vertex p
Sparse exterior extensions of dense nine-critical cores
Let $G$ be biplanar and let $Q$ be an induced nine-vertex-critical subgraph of order at most seventeen with $e(Q)\ge6|V(Q)|-20$. We prove that $G$ is nine-color