CS Paper Radar

A Four-Connected Graph without a Legal System

Qiuyu Chen

cs.DM math.CO ·submitted 2026-09-11 18:33 UTC · v1
theory

Abstract

In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three $K_{3,4}$-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.

Closest papers

Nearest neighbours by meaning across the whole index.

Constrained intersection representations and forbidden patterns

cs.DM math.CO ·2026-11-12 ·Laurent Feuilloley, Michel Habib, Amalia Sorondo
similarity 0.60
Abstract

We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characterized by a finite set of forbidden patterns. Third, we show a dual impossibility result: there exists a pattern-defined class of our hierarchy that admits no intersection representation, if we require this representation to be closed under natural operations such as translation and scaling. However, it turns out that if we allow slightly more exotic intersection representations, then we can find one for this pattern-defined class.

0.30

Obstructions to $k$-colouring $H$-free graphs

cs.DM math.CO ·2026-10-07 ·Iain Beaton, Ben Cameron, Adam van Omme
similarity 0.59
Abstract

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs $H$ such that there are only finitely many minimal obstructions to $3$-colouring $H$-free graphs. In general, the minimal obstructions to $k$-colouring $H$-free graphs are the $(k+1)$-vertex-critical $H$-free graphs, those are, the $H$-free graphs $G$ with $χ(G)=k+1$ but $χ(G-v)=k$ for every vertex in $G$. In this paper we complete the characterization for all $k > 4$ by showing that there are onky finitely $k$-vertex-critical $H$-free graphs if and only if $H$ is an induced subgraph of $P_4+\ell P_1$ for some $\ell \geq 0$.

0.20

Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs

cs.CG math.COcs.DMmath.MG ·2026-10-16 ·James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
top venuetheoryhighly cited similarity 0.58
Abstract · To appear at SODA 2027

String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with $m$ edges admit balanced vertex separators of size $\mathcal{O}(m^{3/4}\sqrt{\log m})$ and conjectured that this bound can be improved to $\mathcal{O}(\sqrt{m})$, which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with $m$ edges admit balanced separators of size $\mathcal{O}(\sqrt{m})$, and more generally obtain analogous $\mathcal{O}(\sqrt{m})$ bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.

0.70

Elementary graphs are chromatic-choosable

cs.DM math.CO ·2026-10-12 ·Narayanan N, Nandana K. Vasudevan, K. Somasundaram
theory similarity 0.57
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

Extremal Asymmetric Depth of Planar Graphs and Hidden Near-Mirror Symmetries of IPR Fullerenes

cs.DM math.COmath.GR ·2026-09-02 ·Ján Pastorek
theorycode/data similarity 0.57
Abstract · 21 pages, 7 figures, 1 table. Includes computer-assisted verification; code available at https://github.com/JanPastorek/asym_depth_fullerene…

Although almost all graphs are asymmetric -- having no nontrivial global automorphisms -- they may still possess local symmetries in the form of isomorphisms between induced subgraphs, i.e., partial automorphisms. We study such local symmetries via asymmetric depth, defined in terms of the maximum rank of a nontrivial partial automorphism. We prove a tight upper bound on asymmetric depth in the class of planar graphs and identify the extremal graphs: duals of IPR fullerenes attain the maximum already on $47$ vertices. Our main structural result concerns the IPR fullerenes that are neither maximally asymmetric nor symmetric. In such a cage no purely local action realises a low asymmetric depth, and we show that the map which does realise it cannot be confined to a small part of the cage either: neither to a single face, nor behind an interface of at most $5-k$ edges, $k \le 3$ being the deficiency. A cage of asymmetric depth $2$ or $3$ is therefore not asymmetric in one place; it carries a broken symmetry invisible to its automorphism group. Such cages are rare -- under $2\%$ of the asymmetric IPR fullerenes at $n = 118$. In all $727$ of them the largest partial automorphism is a near-mirror reflection, which we state as an explicit conjecture. We also extend the asymmetric depth bound to graphs of higher genus.

0.50

There is no $8$-regular $K_3$-irregular graph

cs.DM math.CO ·2026-09-29 ·Artem Hak, Sergiy Kozerenko, Andrii Serdiuk
theory similarity 0.56
Abstract · Updated version, properly adressed range {1..20} for n=20. Any comments are welcome

A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular $K_3$-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities $r \in \{10,11,12\}$ (Stevanović et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for $r \le 7$, provided the first example for $r=9$, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for $r=8$ by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular $K_3$-irregular graphs do exist for all $r \ge 9$. Together with our results, this establishes that an $r$-regular $K_3$-irregular graph exists if and only if $r\geq 9$.

0.46

Characterizing Fixed-Treewidth Planar Graphs

cs.DM math.CO ·2026-11-10 ·Laura Merker, Samuel Schneider, Torsten Ueckerdt
similarity 0.56
Abstract

We give the first inductive characterization of planar graphs of treewidth $k$ for each $k \geq 3$. Our definition generalizes the well-known inductive definition of planar $3$-trees and the recent definition of so-called planar quasi-$4$-trees [Förster, 2024]. As a key step, which may be of independent interest, we show that every planar triangulation $G$ of treewidth $k$ admits a tree decomposition of width $k$ where each adhesion set induces a cycle in $G$. As an application of planar quasi-$4$-trees, we show that planar graphs of treewidth at most $4$ have vertex arboricity at most $2$. That is, the vertex-set of every planar graph of treewidth at most $4$ can be partitioned into two sets that each induce a forest.

0.19

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

cs.DM math.CO ·2026-11-18 ·Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood
theory similarity 0.56
Abstract · 28 pages, 4 figures, written by humans

We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

0.21