2024/10/19 by Yusuf Civan, Civan, Yusuf, Zakir Deniz +5
Mathematics · #05C69 #05E40 #05E45 #13F55 #Algebraic structures and combinatorial models #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2410.15213
openalex publication_date 2024/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A biclique in a graph G is a complete bipartite subgraph (not necessarily induced), and the least positive integer k for which the vertex set of G can be partitioned into at most k bicliques is the biclique vertex partition number bp(G) of G. We prove that the inequality reg(S(G))≥ |G|-bp(G) holds for every graph G, where S(G) is the 1-subdivision graph of G and reg(S(G)) denotes the (Castelnuovo-Mumford) regularity of the graph S(G). In particular, we show that the equality reg(S(B))=|B|-bp(B) holds provided that B is a chordal bipartite graph. Furthermore, for every chordal bipartite graph B, we prove that the independence complex of S(B) is either contractible or homotopy equivalent to a sphere, and provide a polynomial time checkable criteria for when it is contractible, and describe the dimension of the sphere when it is not.