Computes a single nice layout for the full G' (Holton-McKay #0) by
trying sage-planar, sage-spring, and networkx-planar layouts and
picking the one with smallest edge-length coefficient of variation.
Spring layout wins (CV^2 = 0.049).
Then uses the SAME positions for G'_0 and G'_1, with pendant
vertices placed offset from their boundary vertex in the direction
of their cut-edge neighbor. This makes the visual correspondence
between G' and its two halves immediate.
Layout: 3 vertical panels showing G' (with cut edges highlighted),
G'_0, G'_1. Each subgraph draws only its own vertices (no orphan
vertices from the other side); all three share the same x-y limits
so positions align across panels.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a new note describing a cut-and-depth-label procedure for
the dual G' of a maximal planar G:
1. Find a 6-edge cut C in G'.
2. Remove cut edges → G'_0, G'_1.
3. In each G'_i:
a. V_i = degree-2 vertices (vertices incident to exactly 1
cut edge, hence degree 3-1=2 in induced subgraph).
b. For each v ∈ V_i, add a pendant edge to a new vertex.
Label pendants depth 0.
c. BFS-propagate: edges adjacent to a depth-d edge get
depth d+1, until all edges are labelled.
Worked example on Holton-McKay graph #0 (38-vertex non-Hamiltonian
cubic plane graph, dual of a 21-vertex triangulation):
- 128 distinct 6-edge cuts found by greedy search.
- Best matching cut: |S| = 10, cut = 6 edges with 12 distinct
endpoints (6 per side).
- G'_0: 10 + 6 = 16 vertices, max depth 2.
- G'_1: 28 + 6 = 34 vertices, max depth 7.
The procedure mirrors the 4CT cut-and-reglue reducibility scheme:
each G'_i has pendants restoring cubicity at the boundary; the
depth labels organize G'_i into concentric layers by distance to
the cut. This is the dual analogue of plane depth from a level
cycle (cf. the level-cycle generalization discussion).
Files:
experiments/cut_depth_label.py
notes/cut_depth_label.tex (3 pages)
notes/fig_cut_depth_label.png
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Extends Definition 1.2 (level edge) to also define "interlevel edge"
for the primal, and adds Definition 1.3 (level/interlevel dual edge)
classifying dual edges by whether they cross a level or interlevel
primal edge.
Useful downstream: in coloring_nested_tire_graphs, the partial tire
dual's edges can now be classified cleanly as level or interlevel
dual edges using the same vocabulary, instead of ad hoc "interior
annular edge" / "spoke edge" naming.
Paper stays at 4 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Splits the existing plane_depth_sequencing paper into two:
papers/plane_depth/paper.tex (NEW, 4 pages):
- Plane depth definition.
- Level edge, up/down/neutral triangle classification.
- Outerplanarity lemma (formerly Lemma 2.6 of PDS).
- Deep embedding G' definition.
- "Every face of G' is up or down" lemma.
- Unique level edge per face; shared level edge between adjacent faces.
- Quadrilateral decomposition definition with three types
(shallow diamond, deep diamond, S quad).
papers/plane_depth_sequencing/paper.tex (slimmed from 11 → 6 pages):
- Cites plane_depth for all foundational definitions.
- Keeps: slice, move definitions (anchor drop, level add, join,
ring completion), move selection, termination theorem.
papers/coloring_nested_tire_graphs/paper.tex:
- Bibliography updated: cite bauerfeld-depth instead of bauerfeld-pds.
- Two in-text references updated to cite the new outerplanarity
lemma in plane_depth.
Rationale: the outerplanarity / deep-embedding / quadrilateral-
decomposition material is foundational and reused by multiple
papers (and by the proposed level-cycle generalization). The
quadrilateral-sequencing programme is one specific application.
Splitting lets coloring_nested_tire_graphs cite the foundations
cleanly without dragging in the sequencing machinery.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Attempts to prove item 1 (non-emptiness of state at L_n in closed
SR+PDS chains ending at outer triangle). Results:
PROVEN:
- S_3-closure preserved by chain propagation.
- State at L_n is either empty OR equals all 6 permutations of {1,2,3}
(the only non-empty S_3-closed subset of permutations).
- Non-emptiness propagates through intermediate tires under outward
PDS via step-1 saturation.
REMAINING GAP (conjecture, empirically true): state at L_{n-1}
intersects the "perm-paired" subset of T_n's σ_D-projection (the
σ_D values that pair with permutation σ_U). At the final step T_n
has m_n=3 < k_n, so saturation fails — chain state at L_{n-1} could
in principle lie entirely in the (non-perm-paired) parity-matching
σ_D's, but empirically doesn't.
KEY STRUCTURAL FINDING: for T=(3, k), the σ_D's paired with a
permutation σ_U equal exactly the (parity-matching σ_D's) ∩ (T's
σ_D-projection). Verified for k=3..10.
HONEST OBSERVATION: a structural proof of the remaining conjecture
(without invoking 4CT) would constitute a new proof of 4CT under
the SR+PDS modelling assumption. The chain-pigeonhole framework
reduces to this single reachability question.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Investigation of the 'outer triangle absorption' hypothesis from
notes/outer_triangle_absorption.tex:
H2 (T_n alone absorbs anything to 6 perms): REFUTED. T_n=(3,k) alone
has σ_U-projection equal to all 27 elements of {1,2,3}^3.
H1 (chain does real work): TRUE, and structurally explained:
K_3-walk parity invariant (Lemma): in any proper edge 3-coloring
of C_n viewed as a closed walk in K_3, the 3 edge-traversal counts
all have the same parity (follows from each vertex's walk-degree
being even).
σ-color count parity (Corollary): σ at the full n cycle positions
has all-same-parity color counts.
Chain preserves parity (Theorem): forward propagation through SR
tire T=(m,k) maps state with parity matching k to state with parity
matching m, via σ_U + σ_D = σ_total with parities adding mod 2.
Outer-triangle absorption (Main Theorem): at L_n with |L_n|=3,
state has all-odd color counts summing to 3, forcing each count =
1, i.e., σ is a permutation of {1,2,3}.
Empirically verified: 0 parity violations across all chain states
in 3 representative chains (sizes 30-14643).
What's left:
- Non-emptiness: state at L_n EQUALS (not just ⊆) the 6 permutations.
Empirically yes. Likely via S_3-invariance argument.
- SR-correctness for actual G (the modeling gap, not addressed here).
If non-emptiness and SR-correctness are closed, this is a structural
proof of 4CT under the PDS framework — fundamentally different from
Birkhoff/Heesch reducibility.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Note records the closed-chain experiment: forward-propagate state
through SR+PDS tire chains with degenerate-inner T_1 and outer-
triangle T_n (m_n=3). All 10 tested chains converge to the same
final state at L_n — exactly the 6 permutations of {1,2,3}.
Introduces the "outer triangle absorption" framing: distinguishes
H1 (chain-dependent: pigeonhole does real work to filter input to
T_n) vs H2 (T_n-only absorption: T_n's σ_U-projection is intrinsically
the 6 permutations regardless of input). Conjecture: H2 (testable by
single-tire computation).
If H2 holds, items 3-4 of the 4CT-via-tire-decomposition outline
become automatic from local data. If H1, the chain-pigeonhole does
structural work and the question is sharper.
Three-panel figure: (A) closed PDS chain (5,6,5,3) with concentric
levels and source apex; (B) outer-face dual constraint requiring
permutation-of-{1,2,3} on outer triangle; (C) state-size trajectory
showing absorption to 6 at the outer step.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Tested 10 closed PDS chains under SR (degenerate-inner T_1, varied
middle tires, outer-triangle T_n with m_n=3). In all cases:
- Forward state grows in the middle (widest tires), shrinks toward outer.
- Final state at outer-triangle L_n has size EXACTLY 6.
- Those 6 elements are EXACTLY the permutations of {1,2,3}.
- Outer-face dual-vertex constraint (degree-3, distinct colors) is
satisfied in every chain.
This is strong empirical evidence that under SR+PDS, the entire
chain-pigeonhole story closes for 4CT:
step 1 (saturation): proven
step 2 (pairwise): automatic from step 1
step 3 (chain consistency, open): always works
step 4 (closed with outer-triangle constraint): always works,
with the 6 outer-permutations as a clean attractor.
If this holds for all internally 6-connected G under SR (likely from
Birkhoff degree ≥ 5), it's a structural proof path for 4CT for
PDS-decomposable triangulations.
Remaining: prove SR holds for all internally 6-connected G; verify
exhaustively across more chains; find symbolic proof of the
"final state = exactly 6 permutations" attractor behavior.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Redo step 2 and step 3 under SR (no chord effect, the correct model
under PDS where O-faces are not G-faces).
Step 2 (pairwise, 14 cases): all compatible. T_1's γ-side projection
saturates {1,2,3}^γ under outward PDS (m_1 ≥ γ from step 1), so
intersection = T_2's projection, always nonempty.
Step 3 (chain consistency, 10 chains up to 6 tires): all compatible.
Forward propagation along the chain shows monotonically growing
support sizes (roughly 3x per step), never empties. Free choice
accumulates outward.
Implication: chain consistency under SR + PDS is essentially
automatic for "open" chains. The remaining gap is the boundary
condition at the outermost level (e.g., the outer triangle of a
triangulated sphere has only 6 valid σ-permutations); whether the
forward state always contains one of those is the next experiment.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Joint-support analysis on (γ=6, T_1=(m_1=3, antipodal, SP), T_2=(k_2=3, no chord, SP)):
T_1's σ_D space = 18 elements (half of Latin set's 36; saturation-
threshold violated by m_1=3 < γ=6). T_2's σ_U space = 84 elements.
The two are intrinsically disjoint on γ, AND S_3-closure of T_1's
outer-ring colorings is already saturated (all 6 permutations
realised) — so abstract Kempe modification on the outside cannot
enlarge T_1's γ-support. The failure is A-IRREDUCIBLE in the
strict Birkhoff sense.
Significance: the SP failure cases aren't 4CT-relevant obstructions
but modeling artifacts. SP treats non-triangular O-faces as single
G-faces, which is incompatible with maximal-planar G. A faithful
maximal-planar G further triangulates these faces, changing the
face-connector and enlarging σ-supports.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Investigated the 8 surviving triple-partitions of γ at k=k_2=9
(chord (0,3),(3,6) on B_in^(2)). Found a clean structural
description.
CLASSIFICATION of γ-edges by T_2's face structure:
For each O^(2)-face F_i, 2 γ-edges are "internal" to F_i
(their adjacent D-triangles are both in F_i).
For each adjacent face pair (F_i, F_{i+1}), 1 γ-edge is
"boundary" between them.
Total: 2r internal + r boundary = 3r γ-edges = |γ| when k=k_2.
STRUCTURAL DESCRIPTION (Prop face-pair-connection):
Latin ⊆ π_U(T_2) iff the partition has the following form:
- One block per cyclically-adjacent face pair (F_i, F_{i+1}).
- Each block = 1 boundary edge δ_{i,i+1} + 1 internal of F_i
+ 1 internal of F_{i+1}.
- For each face F_i, its 2 internal γ-edges are distributed
one per block (the two blocks involving F_i).
Count: 2^r partitions (each face has 2 choices of how to split
its internals across its 2 adjacent blocks).
AT k = k_2 = 9 (r = 3 faces): 2^3 = 8 partitions, matching the
empirical survivors.
WHY NAIVE CANDIDATES FAIL: The next-D and prev-D candidates from
worst_case_proof_sketch.tex group BOTH internals of one face into
one block (e.g., {0,1,2} = both Internal_{F_A} + δ_{AB}, no internal
F_B). This violates the "one internal per face per block" rule.
IMPLICATION: The König-lift approach can be RESCUED by replacing
the naive candidate F~_2 with any of the 2^r face-pair-connection
partitions. Apply König's theorem on bipartite face-incidence
graph of F_1 vs this new F~_2.
NEXT STEP: prove Prop face-pair-connection for all r, then apply
König lift. This is more leveraged than re-tackling the naive
construction.
Files:
experiments/k9_surviving_analysis.py
notes/k9_surviving_partitions.tex (3 pages)
Note also updates notes/induced_partition_findings.tex to point at
the new structural description.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Tested the candidate induced γ-partition from
worst_case_proof_sketch.tex (Conj t2-induces-partition).
Findings:
1. AT k = k_2 = 6 (antipodal chord, faces 3+3): Candidate
partition (next-D or prev-D) gives Latin ⊆ π_U. ✓
But this is partly coincidental: |π_U| = 90 is so large that
ALL 10 triple-partitions of {0,..,5} have Latin ⊆ π_U.
2. AT k = k_2 = 9 (chords (0,3)(3,6), faces 3+3+3): Candidate
partition FAILS. Only 8 of all 280 triple-partitions of
{0,..,8} have Latin ⊆ π_U, and the candidate is not one of
them. The 8 surviving partitions have no obvious geometric
interpretation.
3. ASYMMETRIC k ≠ k_2 (e.g. k=6, k_2=3): Candidate doesn't
produce a triple-partition at all, and no triple-partition
has Latin ⊆ π_U. Conjecture as stated doesn't cover the
case where the empirical worst-case overlap lives.
Implication: The candidate construction is wrong past k = 6.
Step 3 (prove inclusion) is not the right next move -- we'd
be proving a false statement.
Reassessment of Approach 2: the König-overlap proposition (when
both tires give direct γ-face partitions) is still cleanly proven,
but applies to fewer cases than hoped. The asymmetric pairs that
witness the empirical worst case are not covered.
Both approaches now have known structural obstacles:
- Approach 1 (2-SAT): single open Conjecture 1.5, empirically true.
- Approach 2 (König): natural construction empirically wrong past
k=6, plus asymmetric pairs out of scope.
Honest status: chain pigeonhole has no full proof yet.
Files:
experiments/induced_partition.py
notes/induced_partition_findings.tex (3 pages)
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a side-by-side comparison of the two proof attempts now in
the repo:
Approach 1 (cyclic 2-SAT, in rainbow_proof.tex):
Proves π_D = P_m (perms-per-half) for one antipodal-chord SP
tire when m_1 ≥ m - 1. Open piece: 2-SAT solvability
(Conjecture 1.5).
Approach 2 (König lift, in worst_case_proof_sketch.tex):
Proves |S_1 ∩ S_2| ≥ 6 for two adjacent SP tires sharing γ
when both chords are on γ. Open piece: T_2 induces a
γ-face partition (Conj t2-induces-partition).
Assessment: Approach 2 is more promising because (a) the hard step
is already proven (König's theorem), (b) it proves exactly what we
need (chain-pigeonhole non-emptiness, not the full π_D
characterisation), and (c) it directly explains the empirical
worst-case |S_1 ∩ S_2| = 6 = single S_3-orbit phenomenon.
Approach 1 still has value if we need finer control over π_D's
shape, but for just establishing non-empty overlap Approach 2
suffices.
Both approaches witness the SAME canonical 6-element worst-case
intersection (the rainbow S_3-orbit at γ=6 = the König-lifted
Latin S_3-orbit).
Recommended next move: attack Conj t2-induces-partition. Write
down the candidate induced γ-partition explicitly, verify it
computationally, then prove inclusion via transfer-matrix / fibre
lifting.
Note: two_approaches_comparison.tex (3 pages).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Standalone explanation of what "2-SAT solvability" means in the
context of the rainbow proof (rainbow_proof.tex, Conjecture 1.5):
- Defines 2-SAT in general (boolean variables, 2-variable clauses,
P-time decidable).
- Maps it onto our rainbow proof: variables = orientation bits o_j
at D-positions; clauses = inter-D-position gap constraints; cyclic
chain wraps around T'_ann.
- "Solvable" ⇔ proper edge 3-coloring with given σ exists, i.e.
σ ∈ π_D.
- Cyclic 2-SAT can in principle fail; toy example (3-cycle of
not-equal clauses = odd-cycle 2-coloring obstruction).
- Empirically our system never fails for σ ∈ P_m (6-18 satisfying
orientations per σ at m=6), but a structural proof is open.
- Why it matters: proving Conjecture 1.5 upgrades the rainbow
proof's provisional corollary into a theorem and reduces chain
pigeonhole to the perms-per-half overlap.
Note: two_sat_solvability.tex (3 pages).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Proves the clean piece: when both T1 and T2 give direct all-3 γ-face
partitions of E(γ), the worst-case overlap is ≥ 6, witnessed by
König's edge-coloring theorem on the 3-regular bipartite "face-
incidence graph" G. A proper 3-edge-coloring of G lifts to a Latin
σ on γ satisfying both face partitions, and S_3 symmetry gives 6
distinct such σ.
Identifies the gap: T2's chord is on B_in_2, not on γ, so T2 doesn't
directly give a γ-partition. The proof closes if we exhibit an
"induced γ-partition" determined by T2's annular triangulation —
conjectured but not constructed here.
Also commits chunked enumeration code and threshold-search script
launched separately.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Final tally across γ ∈ {3,...,15,18,21}:
- 2297 total pairs tested
- 48 strict-Latin (all-3-faces) counterexamples
- 0 threshold-satisfying (m_1 ≥ γ AND k_2 ≥ γ) counterexamples (882 such pairs)
Refined conjecture (with m_1 ≥ γ precondition) holds across all tested
threshold-satisfying pairs up to γ = 12. For γ ≥ 13, threshold pairs
were unreachable under the n ≤ 27 memory cap (m_1 ≤ 27 - γ < γ).
All 48 strict-Latin CEs violate the threshold on at least one side,
consistent with the saturation behavior identified in step 1.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Replaces the earlier proof sketch with a clearer attempt that:
1. Corrects the sharp threshold: m_1 >= m - 1 (not m_1 >= m).
Empirically verified for m ∈ {4, 6} across m_1 ≥ m - 1.
2. Proves the ⊆ direction cleanly: each O-face dual vertex has
degree m/2 ≤ 3 in T'_{f'}, so its incident spokes must be
pairwise distinct, putting σ in the "perms-per-half" set P_m.
3. Reduces the ⊇ direction to a cyclic 2-SAT solvability claim
(Conjecture 2sat): for each σ ∈ P_m, find an "orientation"
o ∈ {0,1}^m at the m D-positions such that each length-1 gap
has R_j = L_{j+1} and each length-2 gap has R_j ≠ L_{j+1}.
4. Acknowledges the gap: a naive "all-zero orientation" fails
(e.g. rainbow at m_1 = 6 has the all-zero attempt fail at
gap (4,5)). A satisfying assignment exists in every tested
case (6-18 per σ at m=6, m_1=6) but a clean general proof
awaits. Two routes outlined: S_3-equivariant case analysis,
or global implication-graph analysis.
5. Confirms sharpness with explicit forcing-propagation
counterexample at m=6, m_1=4 (rainbow not in π_D).
6. States provisional corollary: π_D = P_m at m_1 ≥ m - 1
(conditional on Conjecture 2sat); chain pigeonhole reduces
to π_U meeting P_m.
Honest about what's proven (the ⊆ half, the 2-SAT reduction,
the sharpness counterexample) and what's left (the 2-SAT
solvability proof).
Note: rainbow_proof.tex (4 pages).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Counterexample search uncovered:
T1 = (m_1=3, chord=(0,3), SP) at γ=6
has |π_D| = 18, but the conjectured rainbow combined orbit has size 36 —
only 6 of the 36 elements actually lie in π_D, and the literal generator
pattern (1,2,3,2,3,1) is itself missing.
Refined conjecture adds m_1 ≥ m precondition (same threshold from step 1
"saturation iff m ≥ k"). Under this precondition all 44 tested
strict-Latin pairs are still compatible. Pointer to log path included.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Attempts to prove the antipodal-chord rainbow conjecture; result is
nuanced:
1. Upper bound (proven cleanly): pi_D ⊆ {σ : (σ_0..σ_{m/2-1}) and
(σ_{m/2}..σ_{m-1}) are both perms of {1,2,3}}. This follows
from the proper-coloring constraint at the two O-face dual
vertices, each of degree m/2 in T'_{f'}.
2. Lower bound at m_1 ≥ m - 1 (constructive): every σ in the
above set extends to a proper edge 3-coloring of T'_{f'}.
Explicit construction at m=6, m_1=6. In particular rainbow
⊂ pi_D.
3. Counterexample at m_1 ≤ m - 2 (refutes original conjecture):
at m=6, m_1=4, the rainbow σ = (1,2,3,2,3,1) is NOT in pi_D.
Explicit forcing-propagation contradiction: two length-1
inter-D-position gaps on T'_ann force conflicting cycle-edge
colors at a U-position. Empirically |pi_D| = 18 (half the
full set) at m=6, m_1 ∈ {3, 4}.
REVISED conjecture: pi_D equals the full "perm-per-face" set
(containing the rainbow orbit) iff m_1 ≥ m - 1. The threshold
m_1 ≥ m - 1 is sharp. Verified for m=4 (all m_1 ≥ 3) and m=6
(m_1 ≥ 5).
Consequence: chain-pigeonhole at γ length m reduces to a smaller
overlap condition under m_1 ≥ m - 1. The case m_1 < m - 1
remains open -- pi_D still nonempty but the rainbow orbit is
missing; structural characterization of the surviving 18-element
support not addressed.
Note: rainbow_proof_sketch.tex (3 pages).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Promotes the orbit_decomposition finding (rainbow orbit appears in 3
different (T_1, T_2) pairs, all with T_1 = (6, (0,3), SP)) into an
explicit conjecture:
Conjecture (Obs:antipodal-rainbow-conjecture):
For T = (m, (0, m/2), SP) (an antipodal-chord SP tire with m even),
π_D(C(T)) always contains the combined orbit of
(a, b, c, b, c, ..., b, c, a) under S_3 × C_m, with the a-positions
at the chord endpoints and b/c alternating elsewhere.
If true, this gives a uniform structural property of antipodal-chord
SP tires: chain pigeonhole on |γ| = m shared cycles reduces to
"π_U of the other tire meets this fixed orbit." Tested at m = 6 in
3 pairs; the m = 4 direct test (24-element conjectured orbit ⊂
36-element support) is mechanical.
Also adds a forward-pointer paragraph at the end of Obs:rainbow in
tire_fiber_step2.tex referencing orbit_decomposition.tex.
orbit_decomposition.tex: 3 pages -> 3 pages (added Conjecture section
and a "why antipodal?" paragraph).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds Sec. 2 "A conjectural Latin-style substructure" with two
conjectures: (1) for tires whose every O-face has exactly 3 B_in
edges, π_D contains the Latin-flavoured subset L (where each O-face
gets a permutation of {1,2,3}); (2) adjacent tires both satisfying (1)
have compatible projections.
Adds tire_fiber_counterexample_search.py: append-log counterexample
hunt across increasing k with deduplication for resumability. Logs
to counterexample_search.log. Smoke-test data at k≤5 shows
non-all-3 SP-model artifacts produce empty intersections (the
conjecture's "exactly 3 B_in edges per face" precondition fails),
but no strict-Latin counterexample yet.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds orbit_decomposition note + script answering: do structurally
different (T_1, T_2) pairs share the same canonical orbits in
S_1 ∩ S_2?
Findings across the 23 step-2 pairs:
1. EVERY intersection is closed under S_3 color permutation
(structural sanity check, follows from color-symmetry of
proper edge 3-coloring).
2. EVERY S_3-orbit has size exactly 6, with one exception: the
constant orbit {(c,c,c,c) : c ∈ {1,2,3}} of size 3 at γ=4,
T_1=T_2=(4,-,SR). So |S_1 ∩ S_2| = 6 × (# S_3-orbits) almost
always.
3. The RAINBOW orbit (a,b,c,b,c,a) at γ=6 appears in 3 different
(T_1, T_2) pairs -- all with T_1 = (6, (0,3), SP). The two-
chord SP tire (6, (0,2)(3,5), SP) never produces the rainbow
orbit. So rainbow is associated with the antipodal-chord
topology, not the pair as a whole.
4. Other canonical orbits recur across structurally different
pairs. E.g. (1,2,1,3) at γ=4 appears in 7 of 12 tested
γ=4 pairs.
This upgrades the step-2 finding: the intersection isn't just
non-empty -- it has full S_3-symmetric structure, contains at
least one size-6 orbit in essentially all cases, and shares
canonical orbits across varied (T_1, T_2) pairings.
Files:
experiments/orbit_decomposition.py
experiments/orbit_decomposition_data.txt
notes/orbit_decomposition.tex (3 pages)
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Previous figures drew σ as VERTEX colors on a 6-cycle. This was
misleading: σ = (1,2,3,2,3,1) is not a proper vertex 3-coloring of
a hexagon (σ_5 = σ_0 = 1 at adjacent vertices), and the user
correctly flagged this.
σ is the coloring of the 6 *spoke edges* -- the G'-edges of G' that
cross γ, equivalently the 6 edges of γ ⊂ G under the duality
γ-edge ↔ crossing G'-edge.
Adjacent γ-edges meet at γ-vertices, which are not G'-vertices, so
σ has NO proper-coloring constraint on itself. Proper-edge-coloring
constraints live on each tire's full annular cycle, which is longer
than 6 (T_1's is 12, T_2's is 9), with γ-spokes interleaved among
non-γ spokes; that's where the extendibility of σ is actually
checked.
Redrawn figures:
- fig_rainbow_orbit.png: σ drawn as edge colors of γ (not vertex
colors), all 6 orbit elements.
- fig_rainbow_pattern.png: abstract pattern abcbca as edge labels,
with explanatory text in the legend.
- fig_rainbow_setup.png: shows γ between the two tires with each
tire's full annular cycle (length 12 and 9), the interleaved
non-γ dual vertices, the dashed G'-spoke edges crossing γ
colored by σ, and T_1's antipodal chord in O_1.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Bypasses the 3^n brute-force iteration in tire_fiber_chords.py by
directly constructing the 2^n proper edge 3-colorings of C_n via a
vectorized binary-branch numpy build. Benchmarked 146× speedup at n=12,
424× at n=15; brings n=18 to 0.1s and n=24 to 6.6s.
Step-2 extension at k=9 (13 pairs) and k=12 (10 pairs): every tested
pair is compatible (23/23, bringing total to 46/46 with the earlier
note). The S_3-orbit observation extends: the smallest tested
intersection at k=12 is again exactly 6 elements forming a single
S_3-orbit of the pattern (1,2,3,2,2,1,3,3,2,3,1,1) — each of T1's four
chord-induced faces receives a permutation of {1,2,3} as its σ-values,
a "Latin-style" assignment.
Note conjectures a structural theorem: every SP-feasible tire's
projection support contains the "Latin-flavoured" subset where each
O-face sees a permutation of {1,2,3}, and this gives a common
substructure that makes chain-pigeonhole succeed.
Caveat: intersection sizes are all multiples of 6, consistent with the
S_3 invariance of both supports.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds three figures visualising the rainbow-orbit intersection from
tire_fiber_step2.tex (Observation rainbow):
k=6, T_1=(m=6, chord=(0,3), SP) vs T_2=(k=3, no chord, SR)
|S_1 ∩ S_2| = 6 = the S_3-orbit of (a,b,c,b,c,a)
Files:
- fig_rainbow_orbit.png: 6-panel grid showing all 6 orbit elements,
each as a hexagon coloured by the corresponding σ.
- fig_rainbow_pattern.png: abstract pattern abcbca on the shared
cycle γ with explicit position-class legend.
- fig_rainbow_setup.png: geometric setup — T_1 outside γ with its
antipodal chord (v_0, v_3) ∈ O_1, T_2 inside γ (a triangle), and
the orbit element σ = (1,2,3,2,3,1) shown on γ.
Adds experiments/draw_rainbow_orbit.py generator script.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
For pairs (T1, T2) sharing a cycle γ, intersect T1's D-projection
(inner-spoke pattern from outer tire) with T2's U-projection
(outer-spoke pattern from inner tire) on γ. Compatibility = nonempty
intersection.
Result: 23/23 tested pairs are compatible, spanning k ∈ {3,4,5,6},
both SR/SP models, and a range of chord configurations on each side.
Notable: small intersections have clean S_3-orbit structure. Worst
tested case (k=6, antipodal-chord T1 vs unchorded SR T2) has
intersection of size 6 — exactly the 3! rainbow patterns (a,b,c,b,c,a).
This suggests structural rather than accidental overlap, and points to
a theorem worth proving.
Caveats: 23 cases at k≤6 isn't a proof; longer chains (step 3) require
more than pairwise overlap.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Companion to tire_fiber_data.tex. The chord case forces a modelling
choice for the surrounding G: Steiner-rich (each B_in edge gets its
own sub-triangle, chords are invisible to T'_{f'}) vs Steiner-poor
(each O-face is one G-face, chord set determines feasibility).
Under SP, a tire with k > 3 is infeasible unless O already contains
enough chords to keep every O-face at most 3 B_in edges. With chords:
support is positive but much smaller than SR — π_D never reaches 3^k,
and π_D's shrinkage is m-independent. More chords = smaller faces =
MORE support (each chord splits a hard constraint into easier ones).
Side-by-side data table for (m, k) ∈ {3,4,5,6,...}² with various
chord sets, plus 3-page note documenting the modelling choice and
implications for chain pigeonhole.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Step 1 of birkhoff_heesch_reducibility action items. Brute-force
enumerates N(T'_{f'}; σ) for G_n = C_n + n pendants at 3 colors,
n=3..12. Two empirical findings: (1) fiber sizes are always 1 or 2
(constant σ on even n gives size 2; everything else gives size 1);
(2) projecting C onto k evenly-spread positions covers {1,2,3}^k iff
n ≥ 2k. The second implies that for a tire with |B_out| ≥ |B_in|,
every ring coloring on the inner boundary is realisable — so the
chain-pigeonhole intersection step is trivially nonempty whenever the
shared cycle is not locally the longest. Includes script, raw JSON,
text dump, and 4-page data note.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Summarises classical reducibility theory (Birkhoff 1913, Heesch
discharging, Appel-Haken, RSST) in modern notation, then maps it
onto the spoke-fiber decomposition: ring colorings ↔ spoke configs,
good/bad colorings ↔ realisable/unrealisable σ, D-reducibility ↔
chain-pigeonhole conductivity. Honest assessment: framework gives
vocabulary and a Sage-checkable template for small tires, but does
not give a uniform argument across tire sizes.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Decomposes P_e(T'_{f'}, k) into fibers over spoke configurations σ,
specializes to the menagerie §6 formula when there are no spokes, and
sets up the cross-tire compatibility step on shared boundary spokes.
Includes brute-force-verified worked example on C_4 with four pendants.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a new definition partitioning V(T'_{f'}) \ V(f') by geometric
location relative to the face f':
V_out(T'_{f'}) := { v in V(T'_{f'}) \ V(f') : v lies outside the
closure of f' }
= "outer spokes"
V_in(T'_{f'}) := { v in V(T'_{f'}) \ V(f') : v lies inside the
open region f' }
= "inner spokes"
These are well-defined because the boundary walk of f' is V(f') by
definition, so no element of V(T'_{f'}) \ V(f') sits on ∂f'.
In the spoke-only setting (T'_ann = C_{n+m}), the inner spokes of
the inner face are the O-side non-annular dual vertices and the
outer spokes are the source-side non-annular dual vertices (and
vice-versa for the outer face).
Paper stays at 10 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Renames Definition 1.16 from "Partial tire facial dual" to "Tire
annular face connector" to match the family of "tire annular ..."
terminology (cf. Definition 1.15 "Tire annular subgraph").
Symbol T'_{f'} unchanged.
Updates:
- Definition 1.16 title and body wording
- Label changed to def:tire-annular-face-connector
- Figure suptitle in fig_facial_dual_choices.png
- Module docstring of draw_facial_dual_choices.py
Paper stays at 10 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Revert the previous renaming of G'_ann; the symbol is back to
T'_ann. The CONCEPT NAME is changed from "annular dual subgraph"
to "tire annular subgraph" to clarify it's the tire's annular
portion as seen in G'.
Updates:
- Definition 1.15 retitled "Tire annular subgraph"
- Label changed to def:tire-annular-subgraph
- Cross-references in Definition 1.16 and the spoke-only remark
- Figure suptitle reverted to T'_ann
- Regenerated fig_facial_dual_choices.png
Paper stays at 10 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Splits the old Definition 1.15 (which combined the annular dual
subgraph and the partial tire facial dual) into two separate
definitions:
Definition 1.15 (Annular dual subgraph):
G'_ann := G'[{d_f : f ∈ F_ann}], with planar embedding inherited
from G'. Renamed from T'_ann to G'_ann (since it's an induced
subgraph of G', not of T).
Definition 1.16 (Partial tire facial dual):
T'_{f'} := closed G'-neighborhood of V(f') with every G'-edge
incident to V(f'), for f' a face of G'_ann.
Updates all references in paper.tex and in the Figure 5 caption /
figure title; regenerates fig_facial_dual_choices.png.
Paper stays at 10 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds fig_facial_dual_choices.png showing T'_{f'} for the three faces
A, B, C of T'_ann = θ(1, 3, 3) in the bridge case:
Face A (outer): V(A) = all 6 vertices; T'_A pulls in all four
external neighbors u_1, u_2, u_4, u_5.
Face B (inner right): V(B) = {v_0, v_1, v_2, v_3}; T'_B pulls in
only u_1, u_2 and the cycle-neighbors v_4, v_5.
Face C (inner left): mirror image of B.
The figure also visually conveys that the chord endpoints v_0, v_3
(= the two annular faces sharing the bridge edge) have all three
G'-edges inside T'_ann, so neither contributes an external u_v.
Adds:
- experiments/draw_facial_dual_choices.py
- notes/fig_facial_dual_choices.png
- Figure 5 in paper.tex referencing the new image.
Paper grows from 9 to 10 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a new definition formalizing the "partial tire facial dual" T'_{f'}:
(i) Annular dual subgraph T'_ann := G'[{d_f : f ∈ F_ann}], with
planar embedding inherited from G' (where G' is the inner
planar dual of the maximal planar G).
(ii) For each face f' of T'_ann in its inherited embedding,
T'_{f'} := closed G'-neighborhood of V(f') together with
every G'-edge incident to V(f').
Adds a remark noting that in the spoke-only case T'_ann = Γ ≅ C_{n+m}
has two faces (both with V(f') = all interior dual vertices), and
T'_{f'} recovers the planar dual of T when G is the tire plus one
source-side and one O-side face.
Paper stays at 9 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a 'General method' paragraph to menagerie §6 describing how to
compute P_e(G, k) for any G = C_n + (matching of non-crossing chords):
P_e(G, k) = Σ_{(c_1,...,c_r)} N(C_n; forbidden(c_1,...,c_r), k)
where the sum is over chord-color assignments and N counts proper
k-edge-colorings of C_n subject to per-edge forbidden colors (= the
chord colors at adjacent chord endpoints). For each chord-color
choice the inner count is a transfer-matrix product on the polygon,
computed in O(n k^2) time, so the full polynomial is computable in
O(n k^{r+2}) time.
The method specializes to the closed form for θ(1, p, q) (r = 1) and
generalizes to any number of non-crossing chords. Verified against
Sage's chromatic polynomial of the line graph on:
- θ(1, 3, 3): 30
- C_8 + {(0,2), (3,7), (4,6)}: 6
- C_10 + {(0,2), (3,5), (6,8)}: 18
Note grows by ~1/2 page; still 5 pages total.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds a worked example: G = C_8 with three non-crossing chords
{(v_0,v_2), (v_3,v_7), (v_4,v_6)}. Walks through the calculation
of P_e(G, 3) by propagating constraints:
1. Fix chord c_0 = a (3 choices).
2. Forces {c(e_0), c(e_7)} = {b, c} and {c(e_1), c(e_2)} = {b, c}
at v_0 and v_2; cycle constraint at v_1 ties them together.
3. Propagating to chord 3-7 forces c_3 = a and the adjacent
cycle edges to alternate {b, c}.
4. Propagating to chord 4-6 forces c_4 = a and cycle edges
continue the alternation.
Result: cycle edges alternate b, c around C_8 (OK since |C_8| is
even); all 3 chords get the same color a. Total proper 3-edge-
colorings: 3 (choice of a) × 2 (b/c assignment) = 6, verified by
Sage's chromatic-polynomial computation on L(G).
Note that the graph admits a UNIQUE proper 3-edge-coloring modulo
permutation of the 3 colors -- the chord structure forces all
three chords to take the "third" color absent on the polygon cycle.
Adds:
- draw_3chord_example.py
- fig_3chord_example.png
Paper grows from 4 to 5 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds fig_theta133.png illustrating the polygon-with-one-chord case:
hexagon C_6 with the chord between v_0 and v_3 (the two trivalent
vertices), edges colored with a valid proper 3-edge-coloring using
the 3 colors a, b, c. Replaces the previous bracketed placeholder
text in §6 of menagerie.tex.
Adds draw_theta_133.py generator script.
Paper stays at 4 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
θ(1, p, q) IS in the menagerie (= subcubic outerplanar), so the
section about θ being outside no longer applies. Removed:
- menagerie.tex: the entire 'Outside the menagerie' section.
- generate_figures.py: fig_theta function and its main() call.
- fig_theta.png: orphaned figure file.
Note: the paper now ends cleanly with the block-cut decomposition
section. 4 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
User correctly pointed out:
(1) The Figure 4 partial-tire-dual interior structure is not a "theta
graph" in the K_{2,3} sense (which requires all three paths of
length ≥ 2). It is θ(1, 6, 6): a 12-cycle with one chord.
(2) θ(1, p, q) IS outerplanar (just a polygon with one chord), so it
belongs IN the menagerie, not outside it.
Revisions:
- Section 6 ("2-connected outerplanar with Δ ≤ 3"): previously claimed
the class is just cycles; corrected to "cycle, possibly with a
matching of chords." Added explicit description of θ(1, p, q) and
a closed-form for its proper 3-edge-coloring count:
P_e(θ(1,p,q), 3) = (2^{p+q} - 2^p (-1)^q - 2^q (-1)^p + 10 (-1)^{p+q}) / 3.
Verified against Sage's chromatic polynomial for all p, q ∈ {2..6}.
- "Outside the menagerie" section: previously said "theta graphs (all
flavours) are not outerplanar." Corrected to clarify that only
θ(p, q, r) with all three paths of length ≥ 2 (= K_{2,3} subdivisions)
is not outerplanar. Explicitly noted that the bridge-case partial
tire dual gives θ(1, p, q) which IS in the menagerie, with edge-3-
coloring count given by the closed form.
The Figure 4 partial-tire-dual (m=4 outer cycle + barbell O with
bridge) has θ(1, 6, 6) as its interior dual subgraph and so admits
exactly 1326 proper 3-edge-colorings on the interior cycle-with-
chord; leaves contribute their forced colors as in the spoke-only
case.
Paper unchanged. This is a correction within the notes/ subdir only.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Standalone 4-page LaTeX note in notes/menagerie.tex with figures
generated by notes/generate_figures.py, summarizing edge 3-coloring
counts for the menagerie of subcubic outerplanar graphs:
- Path P_n: P_e(P_n, 3) = 3 · 2^{n-2}.
- Cycle C_n: P_e(C_n, 3) = 2^n + 2(-1)^n.
- Star K_{1,3}: P_e = 6.
- Corona C_n ∘ K_1: same as C_n (leaves are forced).
- Trees with Δ ≤ 3: product over BFS-order via greedy.
- 2-connected blocks: just cycles (chords force Δ > 3 generically).
- Block-cut tree decomposition for general subcubic outerplanar.
- Outside the menagerie: theta(2,2,2) = K_{2,3} (not outerplanar),
which is the interior-dual structure of D(T) when O has a bridge.
The note is meant as a quick reference for the partial-tire-dual
paper, particularly for the spoke-only case (corona) and as
motivation for the theta-graph carve-out in the bridge case.
6 small PNG figures included.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
The previous bridge example used a pendant edge as the bridge. A
pendant edge IS technically a bridge (single-edge cut), but the
intended notion was a "proper" non-pendant bridge: an edge cut
connecting two non-trivial subgraphs. Replaced with the smallest
example:
- B_out = 4-cycle on {0, 1, 2, 3}.
- O = barbell on {4..9}: two disjoint triangles {4, 5, 6} and
{7, 8, 9} connected by the bridge edge 6-7.
- Annular triangulation by hand (12 triangles, all listed in the
generator script with planarity verified by Sage).
The barbell case is structurally cleaner: BOTH endpoints of the
bridge have degree >= 2 in O, and the interior dual subgraph has
the two bridge-incident annular faces (d_5, d_6) as its trivalent
theta-graph vertices (in the pendant case, the trivalent vertices
were NOT bridge-incident, which was confusing).
Updates fig_partial_tire_dual_bridge.png and the figure caption.
Paper stays at 9 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds fig_partial_tire_dual_bridge.png beneath the existing partial-
tire-dual figure (Figure 3). The new figure shows a tire graph
whose inner outerplanar O has a bridge:
B_out = triangle on {0, 1, 2};
O = triangle {3, 4, 5} plus pendant edge 5-6 (the bridge);
annular triangulation with 8 triangles (constructed by hand).
Key contrast with the previous figure: because both faces incident
to the bridge are annular triangles, the bridge contributes an
INTERIOR DUAL EDGE rather than two leaves. Consequently the
interior dual subgraph is no longer a single (n+m)-cycle (as in
Prop 1.8 for spoke-only tires) but a theta graph: two trivalent
d_f vertices connected by three internally vertex-disjoint paths.
Leaves come only from B_out (3 of them) and the three non-bridge
triangle edges of O (the inner-triangle face boundary).
Adds experiments/draw_partial_tire_dual_bridge.py to generate the
figure.
Paper grows from 8 to 9 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds Proposition 1.13 (Edge-vertex coloring bijection for D(T)): for
a tire graph T satisfying the spoke-only hypothesis of Prop 1.8 (so
D(T) ~= C_{n+m} ∘ K_1), the number of proper 3-edge-colorings of D(T)
equals the number of proper 3-vertex-colorings of its interior dual
subgraph Γ ~= C_{n+m}, and both equal 2^{n+m} + 2 · (-1)^{n+m}.
Proof: Two bijection steps.
Step 1: Restriction is a bijection between proper 3-edge-colorings
of D(T) and proper 3-edge-colorings of the cycle C_L (where
L = n+m), because at each d_f the leaf's color is forced to be
the unique third color absent from the two cycle edges, and
leaves impose no further constraint.
Step 2: Proper 3-edge-colorings of C_L = proper 3-vertex-colorings
of L(C_L) = proper 3-vertex-colorings of C_L (since L(C_L) ~= C_L).
Step 3: Chromatic polynomial of C_L at k=3 is 2^L + 2 · (-1)^L.
Adds Remark 1.14 noting the closed form depends only on n+m, not
on the specific spoke-only annular triangulation or chord structure
of O.
Empirically verified for L in [3, 10] via Sage's chromatic
polynomials: edge-3-colorings of D(T) = vertex-3-colorings of C_L
= formula in every case.
Paper grows from 7 to 8 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
The complete tire dual D*(T) and Tait correspondence material was
giving exact counts but only via Tait colorings with XOR-to-0
conditions at high-degree vertices -- not proper edge colorings,
which was the original goal. Removed:
- Definition 1.13 (Complete tire dual) and its figure.
- Proposition 1.14 (Tait correspondence on complete tire dual).
- Remark 1.15 (Tait construction).
- Remark 1.16 (octahedron verification).
- Tait1880 bibitem (no longer cited; the body-text mention of
Tait's theorem in the introduction remains).
- experiments/draw_complete_tire_dual.py + its PNG.
- experiments/draw_tait_coloring_example.py + its PNG.
- fig_complete_tire_dual.png from the paper root.
The partial tire dual definition (Def 1.7), structure proposition
(Prop 1.8), figure, and associated scripts (tire_graph.py,
draw_partial_tire_dual.py) are retained.
Paper shrinks from 9 to 7 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds fig_complete_tire_dual.png next to Definition 1.13 of the
complete tire dual. The figure uses the same m=6, k=4 spoke-only
tire as the partial-tire-dual figure (so the two figures can be
directly compared), with the n=6 outer leaves merged into a single
outer-face vertex v_out (blue hexagon, drawn outside the tire) of
degree 6, and the m=4 inner leaves merged into a single inner-face
vertex v_in (red hexagon, drawn at the centre of the inner cycle)
of degree 4.
Generator: experiments/draw_complete_tire_dual.py.
Paper grows from 8 to 9 pages.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
The previous Proposition (Tait correspondence on partial tire dual)
stated equality between non-equivalent 4-vertex-colorings of T and
non-equivalent 3-edge-colorings of D(T). This is wrong as
empirically verified on the octahedron (n=m=3, O=C_3, spoke-only):
- Octahedron: 96 4-vertex-colorings -> 4 classes mod S_4.
- Partial tire dual C_6 ∘ K_1: 66 3-edge-colorings -> 11 classes
mod S_3.
Replaces that proposition with a variant on the COMPLETE tire dual
D*(T) that incorporates non-annular constraints:
Definition 1.13 (Complete tire dual): Quotient D(T)'s leaves into
non-annular-face vertices. Outer leaves merge into a single
outer-face vertex v_out of degree n; for each bounded face F of
O interior to B_in, the corresponding inner leaves merge into
v_F of degree |F|. Equivalently, D*(T) is the planar dual of T.
Proposition 1.14 (Tait correspondence on complete tire dual): the
number of non-equivalent 4-vertex-colorings of T (mod S_4) equals
the number of non-equivalent Tait colorings of D*(T) (mod S_3).
A Tait coloring is an edge labelling by the three nonzero elements
of Z_2 x Z_2 with XOR-to-0 at every vertex of D*(T).
Remark 1.16 (octahedron verification): For octahedron tire,
D*(T) is the cube Q_3. Octahedron has 4 vertex-coloring classes;
Q_3 has 24 proper 3-edge-colorings -> 4 Tait-coloring classes.
Empirically verified via Sage:
- chromatic_polynomial(octahedron)(4) = 96
- chromatic_polynomial(L(Q_3))(3) = 24
The partial tire dual definition (Def 1.7) and its corona-graph
structure proposition (Prop 1.8) are unchanged.
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
Adds Proposition 1.13: the number of non-equivalent proper 4-vertex-
colorings of a tire graph T (mod S_4) equals the number of non-
equivalent proper 3-edge-colorings of its partial tire dual D(T) (mod
S_3). The map is the classical Tait XOR construction: identifying
the four colors with Z_2 x Z_2, each edge of T receives an edge color
equal to the XOR of its endpoint colors, which lies in the three
nonzero elements of Z_2 x Z_2 -- giving the corresponding edge of
D(T) a 3-edge-color. Annular triangles of T, encoded as degree-3
vertices d_f of D(T), supply the three-distinct-colors constraint.
Adds Remark 1.14 explaining the analogy with Tait's classical
correspondence.
Adds Tait 1880 bibitem (Proceedings of the Royal Society of Edinburgh,
vol. 10).
Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
didericis