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.
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...
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
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...
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....
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...
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.