Skip to content
Preprint

Edge ideals of gapfree graphs with matching number $3$

Oct 2026 · 1 citation · ⚡ 1 influential · 22 references
Mathematics

Abstract

We prove that if $G$ is a gapfree graph with matching number $3$, then every power $I(G)^q$, $q\geq2$, of its edge ideal has linear quotients, and hence a linear resolution. Our approach combines graph reductions based on clique domination of gapfree graphs and matching number with operations preserving linear quotients. We reduce the problem to $26$ non-co-chordal graphs on at most seven vertices. A new preservation theorem for gapfree edge addition, together with known results on duplication and gapfree expansion, handles all but one of these graphs. For the remaining graph on seven vertices, we construct a linear quotients ordering for the square and extend it recursively to every higher power.

View source

Similar papers

Preprint Oct 2026

Linear resolutions of powers of edge ideals of gap-free graphs with matching number four

For a finite simple gap-free graph $G$, let $B(G)$ denote the vertices $v$ for which $G-N_G[v]$ is not co-chordal, and put $C(G)=V(G)\setminus B(G)$. We prove a sufficient condition for all ordinary powers of its edge ideal to have linear resolutions from the second power onward: every induced anticycle of length at le...

Luis Alfredo Dupont García · 0 citations
Preprint Nov 2026

Total edge irregularity strength of cubic graphs

We show that every finite simple cubic graph on $n$ vertices has total edge irregularity strength $n/2+1$, confirming the Ivan\v{c}o-Jendrol'conjecture for cubic graphs. The key step is to algorithmically construct a $\{1,n/2+1\}$-vertex labeling such that half of the vertices are labeled $1$ and the average degree of...

A. Barra, S. W. Saputro, Hajime Tanaka · 0 citations
Preprint Oct 2026

A cubic chromatic bound for capped graphs

An ordered graph is capped if, for any four vertices $a<b<c<d$, the edges $ac$ and $bd$ imply the edge $ad$. We prove that every nonempty capped graph $G$ satisfies $\chi(G)\leq\min\{3^{\omega(G)-1},18\omega(G)^3\}$, where $\chi(G)$ and $\omega(G)$ are its chromatic number and clique number. This proves a conjecture of...

Hong-Yang Wang · 0 citations
Preprint Oct 2026

Elementary Proofs of Commonality of the House Graph and $K_4$ with One Edge Subdivided

A graph $H$ is called common if the number of monochromatic copies of $H$ in a $2$-edge-coloring of a large complete graph is asymptotically minimized by the random coloring with an equal proportion of each color. The house graph and $K_4$ with one edge subdivided once are known to be common by the flag algebra method....

Hao Chen · 1 citation
Preprint Oct 2026

Linear circumference in vertex-transitive graphs

We prove that there is an absolute constant $c>0$ such that every connected vertex-transitive graph $G$ on $n \ge 3$ vertices contains a cycle of length at least $cn$. Moreover, every such graph with sufficiently large degree $d$ contains a cycle of length at least $(1-d^{-1/100})n$. This gives the first linear bound t...

Jie Ma, Zi-Yuan Zhao · 2 citations · ⚡1
Preprint Oct 2026

Optimal path decompositions of sparse random graphs

The proof combines a local pairing argument based on the lopsided Lov\'asz local lemma with cycle decompositions of random graphs with cycle decompositions of random graphs.

Ji-Fu Lin, He-Mao Yang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.