Wiley: Journal of Graph Theory: Table of Contents

A Short Proof of Tuza's Conjecture for Weak Saturation in Hypergraphs

Nikolai Terekhov — Wed, 10 Jun 2026 00:22:44 -0700

ABSTRACT

Given an r $r$-uniform hypergraph H $H$ and a positive integer n $n$, the weak saturation number wsat ( n , H ) $\text{wsat}(n,H)$ is the minimum number of edges in an r $r$-uniform hypergraph F $F$ on n $n$ vertices such that the missing edges in F $F$ can be added, one at a time, so that each added edge creates a copy of H $H$. Shapira and Tyomkyn (Proceedings of the American Mathematical Society, 2023) proved Tuza's conjecture on the asymptotic behaviour of wsat ( n , H ) $\text{wsat}(n,H)$. In this paper we provide a significantly shorter proof of the conjecture.

Inducibility of Four‐Vertex Tournaments

Dalton Burke, Bernard Lidický, Florian Pfender, Michael Phillips — Tue, 09 Jun 2026 06:21:34 -0700

ABSTRACT

We determine the inducibility of all tournaments with at most four vertices together with the extremal constructions. The four-vertex tournament containing an oriented C 3 ${C}_{3}$ and one source vertex has a particularly interesting extremal construction, first conjectured by Bożyk, Grzesik, and Kielak. It is an unbalanced blow-up of an edge, where the sink vertex is replaced by a quasi-random tournament and the source vertex is iteratively replaced by a copy of the construction itself.

Towards the Overfull Conjecture

Songling Shan — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

Let G be a simple graph with maximum degree denoted as Δ ( G ). An overfull subgraph H of G is a subgraph satisfying the condition ∣ E ( H ) ∣ > Δ ( G ) ⌊ 1 2 ∣ V ( H ) ∣ ⌋. In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph G with maximum degree Δ ( G ) > 1 3 ∣ V ( G ) ∣ has chromatic index equal to Δ ( G ) if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial-time algorithm for determining the chromatic index of graphs G with Δ ( G ) > 1 3 ∣ V ( G ) ∣, and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make a breakthrough towards the conjecture when not imposing a minimum degree condition on the graph: for any 0 < ε ≤ 1 14, there exists a positive integer n 0 such that if G is a graph on n ≥ n 0 vertices with Δ ( G ) ≥ ( 1 − ε ) n, then the Overfull Conjecture holds for G. The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs G with Δ ( G ) ≥ ∣ V ( G ) ∣ − 3. Our result also implies the Average Degree Conjecture of Vizing from 1968 for the same class of graphs G.

On Strongly and Robustly Critical Graphs

Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list-critical graphs occupy a prominent place in graph coloring theory. Stiebitz, Tuza, and Voigt introduced strongly critical graphs, i.e., graphs that are k-critical yet L-colorable with respect to every non-constant assignment L of lists of size k − 1. Here we strengthen this notion and extend it to the framework of DP-coloring (or correspondence coloring) by defining robustly k-critical graphs as those that are not ( k − 1 )-DP-colorable, but only due to the fact that χ ( G ) = k. We then seek general methods for constructing robustly critical graphs. Our main result is that if G is a critical graph (with respect to ordinary coloring), then the join of G with a sufficiently large clique is robustly critical; this is new even for strong criticality.

An Improved Quasi‐Isometry Between Graphs of Bounded Cliquewidth and Graphs of Bounded Treewidth

Marc Distel — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

Cliquewidth is a dense analogue of treewidth. It can be deduced from recent results by Hickingbotham [arXiv:2501.10840] and Nguyen, Scott, and Seymour [arXiv:2501.09839] that graphs of bounded cliquewidth are quasi-isometric to graphs of bounded treewidth. We improve on this by showing that graphs of cliquewidth k admit a partition with ‘local, but dense’ parts whose quotient has treewidth k − 1. Specifically, each part is contained within a closed neighbourhood of some vertex. We use this to construct a 3-quasi-isometry between graphs of cliquewidth k and graphs of treewidth k − 1. This is an improvement in both the quasi-isometry parameter and the treewidth. We also show that the bound on the treewidth is tight up to an additive constant.

Upper Bounds on the Minimum Size of Feedback Arc Set of Directed Multigraphs With Bounded Degree

Gregory Gutin, Hui Lei, Anders Yeo, Yacong Zhou — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

An oriented multigraph is a directed multigraph without directed 2-cycles. Let fas ( D ) denote the minimum size of a feedback arc set in an oriented multigraph D. In several papers, upper bounds for fas ( D ) were obtained for oriented multigraphs D with maximum degree upper-bounded by a constant. Hanauer conjectured that fas ( D ) ≤ 2.5 n / 3 for every oriented multigraph D with n vertices and maximum degree at most 5. We prove a strengthening of the conjecture: fas ( D ) ≤ m / 3 holds for every oriented multigraph D with m arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor. It would be interesting to determine c such that fas ( D ) ≤ c n for every oriented multigraph D with n vertices and maximum degree at most 5 such that the bound is tight. We show that 5 7 ≤ c ≤ 24 29 < 2.5 3.

Turán Number of Books in Non‐Bipartite Graphs

Lu Miao, Ruifang Liu, Edwin R. van Dam — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

Let ex ( n , H ) be the Turán number of H for a given graph H. A graph is color-critical if it contains an edge whose removal reduces its chromatic number. Simonovits' chromatic critical edge theorem states that if H is color-critical with χ ( H ) = k + 1, then there exists an n 0 ( H ) such that ex ( n , H ) = e ( T n , k ) and the Turán graph T n , k is the only extremal graph provided n ≥ n 0 ( H ). A book graph B r + 1 is a set of r + 1 triangles with a common edge, where r ≥ 0 is an integer. Note that B r + 1 is a color-critical graph with χ ( B r + 1 ) = 3. Simonovits' theorem implies that T n , 2 is the only extremal graph for B r + 1-free graphs of sufficiently large order n. Furthermore, Edwards and independently Khadžiivanov and Nikiforov completely confirmed Erdős' booksize conjecture and obtained that ex ( n , B r + 1 ) = e ( T n , 2 ) for n ≥ n 0 ( B r + 1 ) = 6 r. Recently, Zhai and Lin investigated the problem of booksize from a spectral perspective. Note that the extremal graph T n , 2 is bipartite. Motivated by the above elegant results, we in this paper focus on the Turán problem of non-bipartite B r + 1-free graphs of order n. For r = 0, Erdős proved a nice result: If G is a non-bipartite triangle-free graph on n vertices, then e ( G ) ≤ ( n − 1 ) 2 4 + 1. For general r ≥ 1, we determine the exact value of the Turán number of B r + 1 in non-bipartite graphs and characterize all extremal graphs provided n is sufficiently large. An interesting phenomenon is that the Turán numbers and extremal graphs are completely different for r = 0 and general r ≥ 1.

Long Induced Paths in K s , s‐Free Graphs

Zach Hunter, Aleksa Milojević, Benny Sudakov, István Tomon — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

More than 40 years ago, Galvin, Rival, and Sands showed that every K s , s-free graph containing an n-vertex path must contain an induced path of length f ( n ), where f ( n ) → ∞ as n → ∞. Recently, it was shown by Duron, Esperet, and Raymond that one can take f ( n ) = ( log log n ) 1 / 5 − o ( 1 ). In this note, we give a short self-contained proof that a K s , s-free graph with an n-vertex path contains an induced path of length at least ( log log n ) 1 − o ( 1 ). Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of O ( ( log log n ) 1 + o ( 1 ) ), this essentially resolves this old problem.

Spanning Weakly Even Trees of Graphs

Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

Let G be a graph (with multiple edges allowed) and let T be a tree in G. We say that T is even if every leaf of T belongs to the same part of the bipartition of T, and that T is weakly even if every leaf of T that has maximum degree in G belongs to the same part of the bipartition of T. We confirm two recent conjectures of Jackson and Yoshimoto by showing that every connected graph that is not a regular bipartite graph has a spanning weakly even tree.

On Oriented Colourings of Graphs on Surfaces

Alexander Clow — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

For an oriented graph G, the least number of colours required to oriented colour G is called the oriented chromatic number of G and denoted χ o ( G ). For a non-negative integer g let χ o ( g ) be the least integer such that χ o ( G ) ≤ χ o ( g ) for every oriented graph G with Euler genus at most g. We will prove that χ o ( g ) is nearly linear in the sense that Ω ( g log ( g ) ) ≤ χ o ( g ) ≤ O ( g log ( g ) ). This resolves a question of the author, Bradshaw, and Xu, by improving their bounds of the form Ω ( ( g 2 log ( g ) ) 1 ∕ 3 ) ≤ χ o ( g ) and χ o ( g ) ≤ O ( g 6400 ).

Maximal Line Digraphs

Quentin Japhet, Dimitri Watel, Dominique Barth, Marc‐Antoine Weisser — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

A line digraph L ( G ) = ( A , E ) is the digraph constructed from the digraph G = ( V , A ) such that there is an arc ( a , b ) in L ( G ) if the terminal node of a in G is the initial node of b. The maximum number of arcs in a line digraph with m nodes is ( m / 2 ) 2 + ( m / 2 ) if m is even, and ( ( m − 1 ) / 2 ) 2 + m − 1 otherwise. For m ≥ 7, there is only one line digraph with as many arcs if m is even, and if m is odd, there are two line digraphs, each being the transpose of the other.

Edge‐Length Preserving Embeddings of Graphs Between Normed Spaces

Sean Dewar, Eleftherios Kastis, Derek Kitson, William Sims — Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

The concept of graph embeddability, initially formalized by Belk and Connelly and later expanded by Sitharam and Willoughby, extends the question of embedding finite metric spaces into a given normed space. A finite simple graph G = ( V , E ) is said to be ( X , Y )-embeddable if any set of induced edge lengths from an embedding of G into a normed space Y can also be realised by an embedding of G into a normed space X. This property, being minor-closed, can be characterized by a finite list of forbidden minors. Following the establishment of fundamental results about ( X , Y )-embeddability, we identify sufficient conditions under which it implies independence with respect to the associated rigidity matroids for X and Y. We show that the spaces ℓ 2 and ℓ ∞ serve as two natural extreme spaces of embeddability and discuss ( X , ℓ p )-embeddability for varying p. We provide a complete characterization of ( X , Y )-embeddable graphs for the specific case when X is 2-dimensional and Y is infinite-dimensional.

Tight Bounds for Hypercube Minor‐Universality

Mon, 08 Jun 2026 01:44:35 -0700

ABSTRACT

A graph G is m-minor-universal if every graph H with at most m edges and no isolated vertices is contained as a minor in G. Recently, Benjamini, Kalifa and Tzalik proved that there is an absolute constant c > 0 such that the d-dimensional hypercube Q d is ( c ⋅ 2 d / d)-minor-universal, while there is an absolute constant K > 0 such that Q d is not ( K ⋅ 2 d / d )-minor-universal. We show that Q d does not contain 3-uniform expander graphs with C ⋅ 2 d / d edges as minors. This matches the lower bound up to a constant factor and answers one of their questions.

Issue Information

Mon, 08 Jun 2026 01:44:35 -0700

Journal of Graph Theory, Volume 112, Issue 4, Page 353-355, August 2026.

Semistrong Edge Coloring and (0, 1)‐Relaxed Strong Edge Coloring of Graphs

Yuquan Lin, Wensong Lin — Fri, 05 Jun 2026 04:53:40 -0700

ABSTRACT

In this work, we study two relaxations of the well-known strong edge coloring. A semistrong edge coloring of a graph G $G$ is an edge coloring in which every color class forms a matching M $M$ such that every edge of M $M$ is incident with (at least) one vertex of degree 1 in the subgraph of G $G$ induced by the vertices covered by M $M$. For any two nonnegative integers s $s$ and t $t$, an ( s , t ) $(s,t)$-relaxed strong edge coloring of G $G$ is an edge coloring in which, for every edge e $e$ of G $G$, at most s $s$ edges at distance 1 and at most t $t$ edges at distance 2 from e $e$ receive the same color as e $e$. The corresponding chromatic indices are defined accordingly. We confirm a recent conjecture of Lužar, Mockovčiaková, and Soták [J. Graph Theory 105 (2024) 612-632], which asserts that every connected graph G $G$ with maximum degree Δ ${\rm{\Delta }}$ ( ≥ 3 $\ge \,3$), except for K Δ , Δ ${K}_{{\rm{\Delta }},{\rm{\Delta }}}$, has a semistrong chromatic index at most Δ 2 − 1 ${{\rm{\Delta }}}^{2}-1$. This is achieved by constructing an edge coloring of G $G$ using at most Δ 2 − 1 ${{\rm{\Delta }}}^{2}-1$ colors that is simultaneously semistrong and ( 0 , 1 ) $(0,1)$-relaxed strong. Consequently, every such graph also has ( 0 , 1 ) $(0,1)$-relaxed strong chromatic index at most Δ 2 − 1 ${{\rm{\Delta }}}^{2}-1$.

Tight Minimum Degree Conditions for Apex‐Outerplanar Minors and Subdivisions in Graphs and Digraphs

Chun‐Hung Liu, Youngho Yoo — Tue, 02 Jun 2026 23:09:22 -0700

ABSTRACT

Motivated by Hadwiger's conjecture and related problems for list-coloring, we study graphs H $H$ for which every graph with minimum degree at least ∣ V ( H ) ∣ − 1 $| V(H)| -1$ contains H $H$ as a minor. We prove that a large class of apex-outerplanar graphs satisfies this property. Our result gives the first examples of such graphs whose vertex cover numbers are significantly larger than half the number of its vertices, which breaks a barrier for attacking related coloring problems via extremal functions, and recovers all known such graphs that have arbitrarily large maximum degree. Our proof can be adapted to directed graphs to show that if H → $\overrightarrow{H}$ is the digraph obtained from a directed cycle or an in-arborescence by adding an apex source, then every digraph with minimum out-degree ∣ V ( H → ) ∣ − 1 $| V(\overrightarrow{H})| -1$ contains H → $\overrightarrow{H}$ as a subdivision or a butterfly minor respectively. These results provide the optimal upper bound for the chromatic number and dichromatic number of graphs and digraphs that do not contain the aforementioned graphs or digraphs as a minor, butterfly minor and a subdivision, respectively. Special cases of our results solve an open problem of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé and strengthen results of Gishboliner, Steiner and Szabó.

A Min–Max Relation on Dicuts and Dijoins in Weighted Chordal Digraphs

Gérard Cornuéjols, Siyue Liu, R. Ravi — Tue, 02 Jun 2026 03:25:09 -0700

ABSTRACT

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved. However, the unweighted version conjectured by Woodall remains open. We prove that the Edmonds–Giles conjecture is true if the underlying undirected graph is chordal. We also give a strongly polynomial-time algorithm to construct such a packing.

Automorphism Group of a Wreath Product of Binary Structures

Geňa Hahn, Pierre Ille — Tue, 02 Jun 2026 02:37:47 -0700

ABSTRACT

We consider the question of when the automorphism group of the wreath (lexicographic) product of two structures is the wreath product of the automorphism groups of the two structures. Sabidussi gave partial soluLet us formalize our presentationtions, others (Hemminger, Hahn, Dobson and Morris) continued the work. All the previous work ignored one particular case and here we complete the study by generalizing to binary structures using modular decomposition.

Linear Versus Centred Colouring via Pseudogrids

Tue, 02 Jun 2026 00:59:50 -0700

ABSTRACT

A centred colouring of a graph is a vertex colouring in which every connected subgraph contains a vertex whose colour is unique and a linear colouring is a vertex colouring in which every (not-necessarily induced) path contains a vertex whose colour is unique. For a graph G $G$, the centred chromatic number χ cen ( G ) ${\chi }_{\text{cen}}(G)$ and the linear chromatic number χ lin ( G ) ${\chi }_{\text{lin}}(G)$ denote the minimum number of distinct colours required for a centred, respectively, linear colouring of G $G$. From these definitions, it follows immediately that χ lin ( G ) ≤ χ cen ( G ) ${\chi }_{\text{lin}}(G)\le \,{\chi }_{\text{cen}}(G)$ for every graph G $G$. The centred chromatic number is equivalent to treedepth and has been studied extensively. Much less is known about linear colouring. Kun and colleagues prove that χ cen ( G ) ≤ O ˜ ( χ lin ( G ) 190 ) ${\chi }_{\text{cen}}(G)\le \tilde{O}({\chi }_{\text{lin}}{(G)}^{190})$ for any graph G $G$ and conjecture that χ cen ( G ) ≤ 2 χ lin ( G ) ${\chi }_{\text{cen}}(G)\le 2{\chi }_{\text{lin}}(G)$. Their upper bound was subsequently improved by Czerwiński and colleagues to χ cen ( G ) ≤ O ˜ ( χ lin ( G ) 19 ) ${\chi }_{\text{cen}}(G)\le \tilde{O}({\chi }_{\text{lin}}{(G)}^{19})$. The proof of both upper bounds relies on establishing a lower bound on the linear chromatic number of pseudogrids, which appear in the proof due to their critical relationship to treewidth. Specifically, Kun and colleagues prove that k × k $k\times k$ pseudogrids have linear chromatic number Ω ( k ) ${\rm{\Omega }}(\sqrt{k})$. Our main contribution is establishing a tight bound on the linear chromatic number of pseudogrids, specifically χ lin ( G ) ≥ Ω ( k ) ${\chi }_{\text{lin}}(G)\ge {\rm{\Omega }}(k)$ for every k × k $k\times k$ pseudogrid G $G$. As a consequence we improve the general bound for all graphs to χ cen ( G ) ≤ O ˜ ( χ lin ( G ) 10 ) ${\chi }_{\text{cen}}(G)\le \tilde{O}({\chi }_{\text{lin}}{(G)}^{10})$. In addition, this tight bound gives further evidence in support of Kun and colleagues' conjecture (above) that the centred chromatic number (i.e., the treedepth) of any graph is upper bounded by a linear function of its linear chromatic number.

Stable Cuts, NAC‐Colourings and Flexible Realisations of Graphs

Mon, 01 Jun 2026 06:16:50 -0700

ABSTRACT

A (2-dimensional) realisation of a graph G $G$ is a pair ( G , p ) $(G,p)$, where p $p$ maps the vertices of G $G$ to R 2 ${{\mathbb{R}}}^{2}$. A realisation is flexible if it can be continuously deformed while keeping the edge lengths fixed, and rigid otherwise. We say that G $G$ is rigid if every generic realisation of G $G$ is rigid; otherwise, G $G$ is flexible. In this paper, we investigate the relationship between stable cuts and graphs which are either flexible or admit a flexible (not necessarily generic) realisation with positive edge lengths. We strengthen a result of Chen and Yu, who proved that every n $n$-vertex graph with at most 2 n − 4 $2n-4$ edges has a stable cut, by showing that every flexible graph has a stable cut. The existence of a stable cut is a sufficient, but not necessary, condition for a flexible realisation to exist. Using a result of Le and Pfender on stable cuts, we prove a conjecture of Grasegger, Legerský and Schicho that characterises the minimally rigid graphs that admit a flexible realisation. Additionally, we investigate the number of NAC-colourings in various graphs. A NAC-colouring is a type of edge colouring introduced by Grasegger, Legerský and Schicho, who showed that the existence of such a colouring characterises the existence of a flexible realisation with positive edge lengths. We provide an upper bound on the number of NAC-colourings for arbitrary graphs, and construct families of graphs, including rigid and minimally rigid ones, for which this number is exponential in the number of vertices.

Weak Degeneracy of Planar Graphs

Anton Bernshteyn, Eugene Lee, Evelyne Smith‐Roberge — Thu, 28 May 2026 05:27:21 -0700

ABSTRACT

The weak degeneracy of a graph G $G$ is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for graph coloring. Every d $d$-degenerate graph is weakly d $d$-degenerate, but the converse is not true in general (e.g., all connected d $d$-regular graphs except cycles and cliques are weakly ( d − 1 ) $(d-1)$-degenerate). If G $G$ is weakly d $d$-degenerate, then the list-chromatic number of G $G$ is at most d + 1 $d+1$, and the same upper bound holds for various other parameters such as the DP-chromatic number and the paint number. Here we rectify a mistake in a paper of the first two authors and give a correct proof that planar graphs are weakly 4-degenerate, strengthening the famous result of Thomassen that planar graphs are 5-list-colorable.

Hitting Times in the Binomial Random Graph

Bertille Granet, Felix Joos, Jonathan Schrodt — Fri, 22 May 2026 06:31:18 -0700

ABSTRACT

Fix k ≥ 2 $k\ge 2$, choose log n n ( k − 1 ) ∕ k ≤ p ≤ 1 − Ω ( log 4 n n ) $\frac{\mathrm{log}n}{{n}^{(k-1)\unicode{x02215}k}}\le p\le 1-{\rm{\Omega }}(\frac{{\mathrm{log}}^{4}n}{n})$, and consider G ~ G ( n , p ) $G\unicode{x0007E}G(n,p)$. For any pair of vertices v , w ∈ V ( G ) $v,w\in V(G)$, we give a simple and precise formula for the expected number of steps that a random walk on G $G$ starting at w $w$ needs to first arrive at v $v$. The formula only depends on basic structural properties of G $G$. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing p $p$.

Bipartite Graphs With Minimum Degree at Least 15 Are Antimagic

Kecai Deng — Wed, 20 May 2026 00:19:06 -0700

ABSTRACT

An antimagic labeling of a graph G = ( V , E ) $G=(V,E)$ is a one-to-one mapping f : E → { 1 , 2 , … , ∣ E ∣ } $f:E\to \{1,2,\ldots ,| E| \}$, ensuring that the vertex sums in V $V$ are pairwise distinct, where a vertex sum of a vertex v $v$ is defined as the sum of the labels of the edges incident to v $v$. A graph is called antimagic if it admits an antimagic labeling. The Antimagic Labeling Conjecture, proposed by Hartsfield and Ringel in 1990, posits that every connected graph other than K 2 ${K}_{2}$ is antimagic. The conjecture was confirmed for graphs of average degree at least 4,182 in 2016 by Eccles, where it was stated that a similar approach could not reduce the bound below 1,000 from 4,182. This paper shows that every bipartite graph with minimum degree at least 15 is antimagic. Our approach relies on three tools: a consequence of König's Theorem, the existence of a subgraph of a specific size that avoids Eulerian components, and a labeling lemma that ensures some vertex sums are divisible by three while others are not.

Normal Approximation for Subgraph Count in Random Hypergraphs

Mikołaj Nieradko, Wojciech Michalczuk, Grzegorz Serafin — Tue, 19 May 2026 07:08:15 -0700

ABSTRACT

A nonuniform and inhomogeneous random hypergraph model is considered, which is a straightforward extension of the celebrated binomial random graph model G ( n , p ) ${\mathbb{G}}(n,p)$. We establish necessary and sufficient conditions for the small hypergraph count to be asymptotically normal, and complement them with convergence rates in both the Wasserstein and Kolmogorov distances. Next we narrow our attention to the homogeneous model and relate the obtained results to the fourth moment phenomenon. Additionally, a short proof of the necessity of the aforementioned conditions is presented, which seems to be absent in the literature, even in the context of the model G ( n , p ) ${\mathbb{G}}(n,p)$.

The k $k$‐Radius of 2‐Connected Graphs

Peter Dankelmann, Paul Horn — Tue, 19 May 2026 06:31:11 -0700

ABSTRACT

Let G $G$ be a connected graph. If S $S$ is a set of vertices of G $G$, and v $v$ is a vertex of G $G$, then the distance d ( v , S ) $d(v,S)$ is the distance between v $v$ and a vertex of S $S$ closest to v $v$. The eccentricity of S $S$ is defined as max v ( d ( v , S ) ${\max }_{v}(d(v,S)$. For k ∈ N $k\in {\mathbb{N}}$, the k $k$-radius of G $G$ is defined as the smallest eccentricity of a set of k $k$ vertices of G $G$. The k $k$-radius is, in some sense, a dual to the d $d$-distance domination number of G $G$, defined as the minimum cardinality of a set X $X$ of vertices of G $G$ such that every vertex not in X $X$ is within distance d $d$ of some vertex in X $X$. We prove that the k $k$-radius of a 2-connected graph of order n $n$ is at most n 2 k + O ( 1 ) $\frac{n}{2k}+O(1)$. We also extend the well-known result that the vertex set of a 2-connected graph can be partitioned into two subsets of prescribed order, each inducing a connected subgraph. We prove that if we allow a small overlap between the sets, then the vertex set of a 2-connected graph can be expressed as the union of three subsets of prescribed order, each inducing a connected subgraph.

B‐Coloring of Planar Graphs

Jiangxu Kong, Yiqiao Wang, Mengmeng Zheng — Sat, 16 May 2026 08:12:36 -0700

ABSTRACT

Let q B ( G ) ${q}_{B}(G)$ denote the minimum number of colors needed to properly color the edges of a graph G $G$ such that every 4-cycle is colored with four different colors. Very recently, Gyárfás et al. [3] proved that q B ( G ) ≤ 2 Δ + 8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for a planar graph G $G$ and q B ( G ) ≤ Δ + 1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for an outerplanar graph G $G$ except C 4 ${C}_{4}$ and K 4 − e ${K}_{4}-e$. They also conjectured that, when Δ ${\rm{\Delta }}$ is large enough, every planar graph G $G$ has q B ( G ) ≤ 2 Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ and every outerplanar graph G $G$ has q B ( G ) = Δ ${q}_{B}(G)={\rm{\Delta }}$. Let G $G$ be a planar graph. In this paper, we show the following results: (1) q B ( G ) ≤ 2 Δ + 6 ${q}_{B}(G)\le 2{\rm{\Delta }}+6$; (2) q B ( G ) ≤ 2 Δ + 4 ${q}_{B}(G)\le 2{\rm{\Delta }}+4$ if Δ ≥ 12 ${\rm{\Delta }}\ge 12$; (3) q B ( G ) ≤ 2 Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ if Δ ≥ 38 ${\rm{\Delta }}\ge 38$; (4) q B ( G ) = Δ ${q}_{B}(G)={\rm{\Delta }}$ if G $G$ is outerplanar and Δ ≥ 7 ${\rm{\Delta }}\ge 7$. Results (3) and (4) confirm the conjectures of Gyárfás et al. [3].

Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs

Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou — Thu, 14 May 2026 23:28:24 -0700

ABSTRACT

A bisection of a graph is a cut in which the number of vertices in the two parts of the cut differ by at most 1. In this paper, we consider maximum weight bisections of edge-weighted triangle-free subcubic graphs and show that every weighted triangle-free subcubic graph G = ( V , E , w ) $G=(V,E,w)$ has a bisection with weight at least θ ⋅ w ( G ) $\theta \cdot w(G)$ unless G ≅ K 1 , 3 $G\cong {K}_{1,3}$ (where θ = 613 855 ≈ 0.716959 $\theta =\frac{613}{855}\approx 0.716959$). We conjecture that θ $\theta $ can be replaced by 11 / 15 ≈ 0.73333 $11/15\approx 0.73333$, the value of θ $\theta $ for the Peterson graph and prove the conjecture for weighted bridgeless triangle-free cubic graphs.

On a Clique‐Building Game of Erdős

Alexandru Malekshahian, Sam Spiro — Thu, 14 May 2026 03:02:03 -0700

ABSTRACT

The following game was introduced in a list of open problems from 1983 attributed to Erdős: two players take turns claiming edges of a Kn ${K}_{n}$ until all edges are exhausted. Player 1 wins the game if the largest clique that they claim at the end is strictly larger than the largest clique of their opponent; otherwise, Player 2 wins the game. Erdős conjectured that Player 2 always wins this game for n≥3 $n\ge 3$. We make the first known progress on this problem, proving that this holds for at least 3/4 of all such n $n$. We also address a biased version of this game, as well as the corresponding degree-building game, both of which were originally proposed by Erdős as well.

On the Hardness of Switching to a Small Number of Edges

Vít Jelínek, Eva Jelínková, Jan Kratochvíl — Thu, 14 May 2026 02:54:21 -0700

ABSTRACT

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other one by a sequence of switches. Jelínková et al. [DMTCS 13, no. 2, 2011] presented a proof that it is NP-complete to decide whether the input graph is switching-equivalent to a graph that contains at most a given number of edges. There turns out to be a flaw in their proof. We present a correct proof. Furthermore, we prove that the problem remains NP-complete even when restricted to graphs whose density is bounded from above by an arbitrary fixed constant. This partially answers a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014].

Realizing Degree Sequences With S3 ${{\mathscr{S}}}_{3}$‐Connected Graphs

Rui Guan, Chenglin Jiang, Hong‐Jian Lai, Jiaao Li, Xinyuan Li — Thu, 14 May 2026 02:38:16 -0700

ABSTRACT

A graph G $G$ is S3 ${{\mathscr{S}}}_{3}$-connected if, for any mapping β : V ( G ) ↦ Z 3 $\beta :V(G)\mapsto {{\mathbb{Z}}}_{3}$ with ∑ v ∈ V ( G ) β ( v ) ≡ 0 ( mod 3 ) ${\sum }_{v\in V(G)}\beta (v)\equiv 0\,(\mathrm{mod}\,3)$, there exists a strongly connected orientation D $D$ satisfying d D + ( v ) − d D − ( v ) ≡ β ( v ) ( mod 3 ) ${d}_{D}^{+}(v)-{d}_{D}^{-}(v)\equiv \beta (v)\,(\mathrm{mod}\,3)$ for any v ∈ V ( G ) $v\in V(G)$. It is known that S 3 ${{\mathscr{S}}}_{3}$-connected graphs are contractible configurations for the property of flow index strictly less than three. In this paper, we provide a complete characterization of graphic sequences that have an S 3 ${{\mathscr{S}}}_{3}$-connected realization: A graphic sequence π = ( d 1 , … , d n ) $\pi =({d}_{1},\ldots ,{d}_{n})$ has an S 3 ${{\mathscr{S}}}_{3}$-connected realization if and only if min { d 1 , … , d n } ≥ 4 $\min \{{d}_{1},\ldots ,{d}_{n}\}\ge 4$ and ∑ i = 1 n d i ≥ 6 n − 4 ${\sum }_{i=1}^{n}{d}_{i}\ge 6n-4$. Consequently, every graphic sequence π = ( d 1 , … , d n ) $\pi =({d}_{1},\ldots ,{d}_{n})$ with min { d 1 , … , d n } ≥ 6 $\min \{{d}_{1},\ldots ,{d}_{n}\}\ge 6$ has a realization G $G$ with flow index strictly less than three. This supports the conjecture of Li, Thomassen, Wu and Zhang [European J. Combin., 70 (2018) 164-177] that every 6-edge-connected graph has a flow index strictly less than three.

On Deep‐Commuting Graph of Groups

Bahram Arvin, Behrouz Edalatzadeh, Ali Reza Salemkar — Fri, 08 May 2026 06:51:32 -0700

ABSTRACT

The deep-commuting graph DCom ( G ) $\text{DCom}(G)$ of a finite group G $G$ is the graph with vertex set G $G$ such that two vertices x $x$ and y $y$ are adjacent if their inverse images in every central extension of G $G$ commute. In this paper, we determine the structure of the deep-commuting graph of the direct product of groups with respect to the graphs of the given groups. Also, we see that nonisomorphic finite groups may have isomorphic deep-commuting graphs, however, finite abelian groups with isomorphic deep-commuting graphs are isomorphic.

A Coarse Geometric Approach to Graph Layout Problems

Wanying Huang, David Hume, Samuel J. Kelly, Ryan Lam — Tue, 05 May 2026 23:23:39 -0700

ABSTRACT

We define a range of new coarse geometric invariants based on various graph–theoretic measures of complexity for finite graphs, including treewidth, pathwidth, cutwidth and bandwidth. We prove that, for bounded degree graphs, these invariants can be used to define functions which satisfy a strong monotonicity property, namely, they are monotonically nondecreasing with respect to a large-scale geometric generalisation of graph inclusion, and as such have potential applications in coarse geometry and geometric group theory. On the graph–theoretic side, we prove asymptotically optimal bounds on most of the above widths for the family of all finite subgraphs of any bounded degree graph whose separation profile is known to be of the form r a log ( r ) b ${r}^{a}\mathrm{log}{(r)}^{b}$ for some a > 0 $a\gt 0$. This large class includes Diestel–Leader graphs, all Cayley graphs of nonvirtually cyclic polycyclic groups, uniform lattices in almost all connected unimodular Lie groups, and many hyperbolic groups.

Anti‐Directed Cycle‐Factors in Oriented Graphs

Ming Chen — Tue, 05 May 2026 06:43:44 -0700

ABSTRACT

Let C ℓ ¯ $\bar{{C}_{\ell }}$ be the anti-directed cycle on ℓ $\ell $ vertices (an orientation in which consecutive edges alternate direction). In 1980, Grant initiated the study of anti-directed cycles in digraphs. We show that for any ℓ ∈ N $\ell \in {\mathbb{N}}$, there exists n 0 ${n}_{0}$ such that any n $n$-vertex oriented graph D $D$ with ℓ ∣ n ≥ n 0 $\ell | n\ge {n}_{0}$ and δ 0 ( D ) ≥ ( 1 3 + o ( 1 ) ) n ${\delta }^{0}(D)\ge (\frac{1}{3}+o(1))n$ contains a C ℓ ¯ $\bar{{C}_{\ell }}$-factor. In particular, the degree condition is asymptotically sharp.

Orientations of Graphs With at Most One Directed Path Between Every Pair of Vertices

Barbora Dohnalová, Jiří Kalvoda, Gaurav Kucheriya, Sophie Spirkl — Tue, 05 May 2026 06:42:20 -0700

ABSTRACT

Given a graph G $G$, we say that an orientation D $D$ of G $G$ is a KT orientation if, for all u , v ∈ V ( D ) $u,v\in V(D)$, there is at most one directed path (in any direction) between u $u$ and v $v$. Graphs that admit such orientations have been used to construct graphs with large chromatic number and small clique number that served as counterexamples to various conjectures. Motivated by this, we consider which graphs admit KT orientations (named after Kierstead and Trotter). In particular, we construct a graph family with small independence number (sub-linear in the number of vertices) which admits a KT orientation. We show that the problem of determining whether a given graph admits a KT orientation is NP-complete, even if we restrict ourselves to planar graphs. Finally, we provide an algorithm to decide if a graph with maximum degree at most 3 admits a KT orientation, whereas, for graphs with maximum degree 4, the problem remains NP-complete.

Maximum Spread of K r ${K}_{r}$‐Minor Free Graphs

Wenyan Wang, Lele Liu, Yi Wang — Thu, 30 Apr 2026 02:46:49 -0700

ABSTRACT

The spread of a graph is the difference between the largest and smallest eigenvalues of its adjacency matrix. In this paper, we investigate spread problems for graphs with excluded clique-minors. We show that for sufficiently large n $n$, the n $n$-vertex K r ${K}_{r}$-minor free graph with maximum spread is the join of a clique and an independent set, with r − 2 $r-2$ and n − r + 2 $n-r+2$ vertices, respectively.

Halin's Grid Theorem for Digraphs

Florian Reich — Wed, 29 Apr 2026 01:15:38 -0700

ABSTRACT

Halin showed that every thick end of every graph contains an infinite grid. We extend Halin's theorem to digraphs. More precisely, we show that for every infinite family ℛ ${\rm{ {\mathcal R} }}$ of disjoint equivalent out-rays there is a grid whose vertical rays are contained in ℛ ${\rm{ {\mathcal R} }}$. Furthermore, we obtain similar results for in-rays and necklaces.

On Tight Tree‐Complete Hypergraph Ramsey Numbers

Jiaxi Nie — Tue, 28 Apr 2026 03:31:05 -0700

ABSTRACT

Chvátal showed that for any tree T $T$ with k $k$ edges, the Ramsey number R ( T , n ) = k ( n − 1 ) + 1 $R(T,n)=k(n-1)+1$. For r = 3 $r=3$ or 4, we show that, if T $T$ is an r $r$-uniform nontrivial tight tree, then the hypergraph Ramsey number R ( T , n ) = Θ ( n r − 1 ) $R(T,n)={\rm{\Theta }}({n}^{r-1})$. The 3-uniform result comes from observing a construction of Cooper and Mubayi. The main contribution of this paper is the 4-uniform construction, which is inspired by the Cooper–Mubayi 3-uniform construction.

Vertex‐Distinguishing and Sum‐Distinguishing Edge Coloring of Regular Graphs

Yuping Gao, Songling Shan, Guanghui Wang — Sat, 25 Apr 2026 05:56:56 -0700

ABSTRACT

Given an integer k ≥ 1 $k\ge 1$, an edge-k $k$-coloring of a graph G $G$ is an assignment of k $k$ colors 1 , … , k $1,\ldots ,k$ to the edges of G $G$ such that no two adjacent edges receive the same color. A vertex-distinguishing (resp. sum-distinguishing) edge-k $k$-coloring of G $G$ is an edge-k $k$-coloring such that for any two distinct vertices u $u$ and v $v$, the set (resp. sum) of colors taken from all the edges incident with u $u$ is different from that taken from all the edges incident with v $v$. The vertex-distinguishing chromatic index (resp. sum-distinguishing chromatic index), denoted χ v d ′ ( G ) ${\chi }_{vd}^{^{\prime} }(G)$ (resp. χ s d ′ ( G ) ${\chi }_{sd}^{^{\prime} }(G)$), is the smallest value k $k$ such that G $G$ has a vertex-distinguishing edge-k $k$-coloring (resp. sum-distinguishing edge-k $k$-coloring). Let G $G$ be a d $d$-regular graph on n $n$ vertices, where n $n$ is even and sufficiently large. We show that χ v d ′ ( G ) = d + 2 ${\chi }_{vd}^{^{\prime} }(G)=d+2$ if d $d$ is arbitrarily close to n / 2 $n/2$ from above, and χ s d ′ ( G ) = d + 2 ${\chi }_{sd}^{^{\prime} }(G)=d+2$ if d ≥ 2 n 3 $d\ge \frac{2n}{3}$. Our first result strengthens a result of Balister et al. for such class of regular graphs, and our second result constitutes a significant advancement in the field of sum-distinguishing edge coloring. To achieve these results, we introduce novel edge coloring results which may be of independent interest.

Turán Problems for Suspension of a Balanced Tree

Xiutao Zhu, Xiaolin Wang, Yanbo Zhang, Fangfang Zhang — Fri, 24 Apr 2026 05:50:43 -0700

ABSTRACT

The Turán number ex ( n , H ) $\text{ex}(n,H)$ is the maximum number of edges that an n $n$-vertex H $H$-free graph can have. The suspension H ^ $\hat{H}$ is obtained from H $H$ by adding a new vertex which is adjacent to all vertices of H $H$ and a tree T $T$ is balanced if the size of one color class is k $k$ and the other is k $k$ or k + 1 $k+1$. In this paper, we obtain a sharp bound of ex ( n , T ^ ) $\text{ex}(n,\hat{T})$ when n ≥ 4 ( 4 k ) 6 $n\ge 4{(4k)}^{6}$ based on the Erdős-Sós Conjecture. We also show the bound is sharp for infinitely many n $n$ and characterize all extremal graphs. In particular, if T $T$ satisfies some conditions such as T $T$ contains a matching covering all vertices in one color class, then the bound is sharp for all n $n$. This is a new class of graphs whose decomposition family does not contain a linear forest but we still can determine its Turán number.

Counterexamples to Two Conjectures on Mean Color Numbers of Graphs

Wushuang Zhai, Yan Yang — Thu, 23 Apr 2026 00:35:18 -0700

ABSTRACT

The mean color number of an n $n$-vertex graph G $G$, denoted by μ(G) $\mu (G)$, is the average number of colors used in all proper n $n$-colorings of G $G$. For any graph G $G$ and any vertex w $w$ in G $G$, Dong (2003) conjectured that (1) μ(G)≥μ((G−w)∪K1) $\mu (G)\ge \mu ((G-w)\cup {K}_{1})$; (2) if w $w$ is not an isolated vertex, then μ(G)≥μ(H) $\mu (G)\ge \mu (H)$, where H $H$ is a graph obtained from G $G$ by deleting all but one of the edges incident to w $w$. We disprove these two conjectures by providing an infinite family of counterexamples.

Signed Projective Cubes, a Homomorphism Point of View

Meirun Chen, Reza Naserasr, Alessandra Sarti — Tue, 21 Apr 2026 23:02:22 -0700

ABSTRACT

The (signed) projective cubes, as a special class of graphs closely related to the hypercubes, are on the crossroad of geometry, algebra, discrete mathematics and linear algebra. Defined as Cayley graphs on binary groups, they represent basic linear dependencies. Capturing the four-color theorem as a homomorphism target they show how mapping of discrete objects, namely graphs, may relate to special mappings of plane to projective spaces of higher dimensions. In this work, viewed as a signed graph, first we present a number of equivalent definitions each of which leads to a different development. In particular, the new notion of common product of signed graphs is introduced which captures both Cartesian and tensor products of graphs. With a nonstandard use of homomorphism between signed projective cubes, we show that they all have circular chromatic number 4. Observing that the 4-color theorem is about mapping planar graphs into S P C ( 2 ) $SPC(2)$, we study some conjectures in extension of 4CT and show the importance of extended double cover operation in formulating such conjectures. As a particular corollary we build a highly symmetric triangle-free graph on 12 vertices admitting a homomorphism from every planar graph of odd girth at least 7. Considering their connection to algebraic geometry, we observe that P C ( 4 ) $PC(4)$, widely known as the Clebsh graph, also known as Greenwood-Gleason graph, is the intersection graph of the 16 straight lines of an algebraic surface known as Segre surface, which is a Del Pezzo surface of degree 4. Noting that the Clebsch surface is one of the most symmetric presentations of a cubic surface all of which contains 27 lines. Hence, from hereafter, we believe, a proper name for P C ( 4 ) $PC(4)$ should be Segre graph.

Fractional List Packing for Layered Graphs

Stijn Cambie, Wouter Cames van Batenburg — Sun, 19 Apr 2026 09:01:34 -0700

ABSTRACT

The fractional list packing number χ ℓ • ( G ) ${\chi }_{\ell }^{\bullet }(G)$ of a graph G $G$ is a graph invariant that has recently arisen from the study of disjoint list-colourings. It measures how large the lists of a list-assignment L : V ( G ) → 2 N $L:V(G)\to {2}^{{\mathbb{N}}}$ need to be to ensure the existence of a “perfectly balanced” probability distribution on proper L $L$-colourings, that is, such that at every vertex v $v$, every colour appears with equal probability 1 / ∣ L ( v ) ∣ $1/| L(v)| $. In this work we give various bounds on χ ℓ • ( G ) ${\chi }_{\ell }^{\bullet }(G)$, which admit strengthenings for correspondence and local-degree versions. As a corollary, we improve theorems on the related notion of flexible list colouring. In particular we study Cartesian products and d $d$-degenerate graphs, and we prove that χ ℓ • ( G ) ${\chi }_{\ell }^{\bullet }(G)$ is bounded from above by the pathwidth of G $G$ plus one. The correspondence analogue of the latter is false for treewidth instead of pathwidth.

Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs

Reza Naserasr, Lan Anh Pham, Cyril Pujol, Huan Zhou — Sat, 18 Apr 2026 08:10:08 -0700

ABSTRACT

A balanced ( p , q ) $(p,q)$-coloring of a signed graph ( G , σ ) $(G,\sigma )$ is an assignment of q $q$ colors to each vertex of G $G$ from a platter of p $p$ colors, such that each color class induces a balanced set (a set that does not induce a negative cycle). The fractional balanced chromatic number of ( G , σ ) $(G,\sigma )$, denoted χ f b ( G , σ ) ${\chi }_{fb}(G,\sigma )$, is the minimum ratio p / q $p/q$ such that ( G , σ ) $(G,\sigma )$ has a balanced ( p , q ) $(p,q)$-coloring. This value is bounded by the fractional arboricity of G $G$, denoted a f ( G ) ${a}_{f}(G)$, which is defined so that each color class induces an acyclic subgraph of G $G$. In this work we present an example of a signed planar simple graph of fractional balanced chromatic number greater than 2, in particular, refuting a conjecture of Bonamy, Kardoš, Kelly, and Postle suggesting that the fractional arboricity of planar graphs is bounded above by 2. By iterating the construction, we show that the supremum of the fractional balanced chromatic number of signed planar simple graphs is at least 83 41 = 2 + 1 41 $\frac{83}{41}=2+\frac{1}{41}$. Our method results in a construction of a planar graph on 34 vertices whose fractional arboricity is 2 + 2 25 $2+\frac{2}{25}$.