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 least five must contain an edge with both endpoints in $C(G)$. The argument uses variable generators of augmented colon ideals to eliminate anticycles that may persist in the ordinary quadratic colons. It yields linear resolutions for all powers $I(G)^q$, $q\ge2$, whenever the ordinary matching number is at most four, which answers the first part of a question of Erey, H\`a, Hibi, Kara and Morey. The criterion also applies to certain graphs with adjacent exceptional vertices and matching number five. The proofs are theoretical and valid over arbitrary fields. We do not assert linear quotients.
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 quotient...
We construct an explicit minimal cellular resolution for every squarefree monomial ideal generated in degree $n-2$ in the polynomial ring $S=K[x_1,\ldots,x_n]$. Such an ideal is the complementary edge ideal $I_c(G)$ of a simple graph $G$ on $[n]$, and the resolution is supported on a labeled regular CW complex $X_G$ of...
The \emph{enhanced power graph} $\PE(G)$ of a finite group $G$ has vertex set $G$, two elements being adjacent if and only if they generate a cyclic subgroup. We determine the finite simple groups $G$ for which $\PE(G)$ is chordal: they are the cyclic groups of prime order, $\Alt(7)$, $\PSL_2(q)$ ($q\ge4$), $\Sz(q)$ ($...
We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=\chi(G)=\omega(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\ge\omega(G)$, every proper precoloring of $S$ extends to a proper coloring of $G$ from arbitrary lists of size $k$ on $V(G)\setminus S$. The proof has three colori...
Suchismita Mishra, N. Narayanan, Umesh Shankar· 0 citations
For a graph $G$, let $f_t(G)$ denote the minimum of the maximum degree of an induced subgraph with $\alpha(G)+t$ vertices, where $\alpha(G)$ is the independence number, and write $f(G)=f_1(G)$. Huang's theorem gives $f(Q_k)\ge\lceil\sqrt{k}\rceil$ for the $k$-dimensional hypercube $Q_k$. We extend this lower bound to C...
Let $G$ be a simple graph with cover ideal $J(G)$ in a polynomial ring $S = \k[x_1, \ldots, x_n]$. For each integer $t \ge 1$, let $\alpha_t(G)$ denote the maximum size of an ordered matching $M$ of $G$ with alternating path length $\ell(M) \le 2t - 1$. Hang, Tam, and Vu established that \[ \operatorname{depth}\!\left(...
H. Nguyen, T. Nguyễn, Thanh Vu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.