Prime graphs, matchings and the Castelnuovo-Mumford regularity Turker Biyikouglu, Yusuf Civan Journal of Commutative Algebra, 2019 We demonstrate the effectiveness of prime graphs for the calculation of the (Castelnuovo-Mumford) regularity of graphs. Such a notion allows us to reformulate the regularity as a generalized induced matching problem and perform regularity calculations in specific graph classes, including $(C_3,P_5)$-free graphs, $P_6$-free bipartite graphs and all Cohen-Macaulay graphs of girth at least five. In particular, we verify that the five cycle graph $C_5$ is the unique connected graph satisfying the inequality $im (G)\lt \mbox {reg}(G)=m (G)$. In addition, we prove that, for each integer $n\geq 1$, there exists a vertex decomposable perfect prime graph $G_n$ with $\mbox {reg}(G_n)=n$.
Coloring hypercomplete and hyperpath graphs Yusuf CİVAN, Demet TAYLAN Turkish Journal of Mathematics, 2014 Given a graph G with an induced subgraph H and a family F of graphs, we introduce a (hyper)graph HH(G;F)=(VH, EH), the hyper-H (hyper)graph of G with respect to F, whose vertices are induced copies of H in G, and \\{H1,H2,\\ldots,Hr\\} \\in EH if and only if the induced subgraph of G by the set \\cupi=1r Hi is isomorphic to a graph F in the family F, and the integer r is the least integer for F with this property. When H is a k-complete or a k-path of G, we abbreviate HKk(G;F) and HPk(G;F) to Hk(G;F) and HPk(G;F), respectively. Our motivation to introduce this new (hyper)graph operator on graphs comes from the fact that the graph Hk(Kn;\\{K2k\\}) is isomorphic to the ordinary Kneser graph K(n;k) whenever 2k \\leq n. As a generalization of the Lovasz--Kneser theorem, we prove that c(Hk(G;\\{K2k\\}))=c(G)-2k+2 for any graph G with w(G)=c(G) and any integer k\\leq \\lfloor w(G)/2\\rfloor. We determine the clique and fractional chromatic numbers of Hk(G;\\{K2k\\}), and we consider the generalized Johnson graphs Hr(H;\\{Kr+1\\}) and show that c(Hr(H;\\{Kr+1\\}))\\leq c(H) for any graph H and any integer r< w(H). By way of application, we construct examples of graphs such that the gap between their chromatic and fractional chromatic numbers is arbitrarily large. We further analyze the chromatic number of hyperpath (hyper)graphs HPk(G;Pm), and we provide upper bounds when m=k+1 and m=2k in terms of the k-distance chromatic number of the source graph.
Vertex-decomposable graphs, codismantlability, cohen-macaulayness, and castelnuovo-mumford regularity Türker Bıyıkoğlu, Yusuf Civan Electronic Journal of Combinatorics, 2014 We call a vertex $x$ of a graph $G=(V,E)$ a codominated vertex if $N_G[y]\subseteq N_G[x]$ for some vertex $y\in V\backslash \{x\}$, and a graph $G$ is called codismantlable if either it is an edgeless graph or it contains a codominated vertex $x$ such that $G-x$ is codismantlable. We show that $(C_4,C_5)$-free vertex-decomposable graphs are codismantlable, and prove that if $G$ is a $(C_4,C_5,C_7)$-free well-covered graph, then vertex-decomposability, codismantlability and Cohen-Macaulayness for $G$ are all equivalent. These results complement and unify many of the earlier results on bipartite, chordal and very well-covered graphs. We also study the Castelnuovo-Mumford regularity $reg(G)$ of such graphs, and show that $reg(G)=im(G)$ whenever $G$ is a $(C_4,C_5)$-free vertex-decomposable graph, where $im(G)$ is the induced matching number of $G$. Furthermore, we prove that $H$ must be a codismantlable graph if $im(H)=reg(H)=m(H)$, where $m(H)$ is the matching number of $H$. We further describe an operation on digraphs that creates a vertex-decomposable and codismantlable graph from any acyclic digraph. By way of application, we provide an infinite family $H_n$ ($n\geq 4$) of sequentially Cohen-Macaulay graphs whose vertex cover numbers are half of their orders, while containing no vertex of degree-one such that they are vertex-decomposable, and $reg(H_n)=im(H_n)$ if $n\geq 6$. This answers a recent question of Mahmoudi et al.
KO-groups of bounded flag manifolds Turkish Journal of Mathematics, 2002
RECENT SCHOLAR PUBLICATIONS
Chordal bipartite graphs, biclique vertex partitions and Castelnuovo-Mumford regularity of -subdivision graphs Y Civan, Z Deniz, O Duginov, MA Yetim arXiv preprint arXiv:2410.15213 , 2024 2024 Citations: 1
Gated independence in graphs Y Civan, Z Deniz, MA Yetim Discrete Applied Mathematics 353, 121-138 , 2024 2024 Citations: 1
Domination versus edge domination on claw-free graphs Y Civan, Z Deniz, MA Yetim Discrete Applied Mathematics 337, 171-172 , 2023 2023 Citations: 2
Order-sensitive domination in partially ordered sets and graphs Y Civan, Z Deniz, MA Yetim Order 40 (1), 157-172 , 2023 2023 Citations: 1
The v -number and Castelnuovo–Mumford regularity of graphs Y Civan Journal of Algebraic Combinatorics 57 (1), 161-169 , 2023 2023 Citations: 26
Bounding the collapsibility number of simplicial complexes and graphs T BIYIKOĞLU, Y Civan 2022 Citations: 1
Bounding the collapsibility number of simplicial complexes and graphs T Bıyıkoğlu, Y Civan arXiv preprint arXiv:2201.13046 , 2022 2022
Bounding the chromatic number of squares of K4-minor-free graphs Y Civan, Z Deniz, MA Yetim Discrete Mathematics 342 (7), 1894-1903 , 2019 2019 Citations: 6
Prime graphs, matchings and the Castelnuovo-Mumford regularity T BIYIKOĞLU, Y Civan Journal of Commutative Algebra 11 (1), 1-27 , 2019 2019 Citations: 1
A NOTE ON THE RECOGNITION OF CODISMANTLABLE GRAPHS AND POSETS T BIYIKOGLU, Y CIVAN 2016
Projective dimension of (hyper) graphs and the Castelnuovo-Mumford regularity of bipartite graphs T Bıyıkoğlu, Y Civan arXiv preprint arXiv:1605.02956 , 2016 2016 Citations: 2
Castelnuovo-Mumford regularity of graphs T Biyikoglu, Y Civan arXiv preprint arXiv:1503.06018 , 2015 2015 Citations: 18
Çizgilerin Castelnuovo-Mumford regülaritesi ve döngü-kıran komplekslerin topolojisi Y Civan, T Bıyıkoğlu TÜBİTAK-Türkiye Bilimsel ve Teknolojik Araştırma Kurumu , 2014 2014
Coloring hypercomplete and hyperpath graphs Y Civan, D Taylan Turkish Journal of Mathematics 38 (1), 1-15 , 2014 2014 Citations: 3
Upper maximal graphs of posets Y Civan Order 30 (2), 677-688 , 2013 2013 Citations: 7
Bounding Castelnuovo-Mumford regularity of graphs via Lozin's transformation T Biyikoglu, Y Civan arXiv preprint arXiv:1302.3064 , 2013 2013 Citations: 12
ODTÜ-BİLKENT Algebraic Geometry Seminar AS Sertöz, Ö Kişisel, Y Ozan, F Arslan, H Önsiper, A Degtyarev, ... 2012
Vertex decomposable graphs, codismantlability, Cohen-Macaulayness and Castelnuovo-Mumford regularity T Biyikoglu, Y Civan arXiv preprint arXiv:1205.5631 , 2012 2012 Citations: 52
Four-cycled graphs with topological applications T Bıyıkoğlu, Y Civan Annals of Combinatorics 16 (1), 37-56 , 2012 2012 Citations: 5
AMS Subject Classification: 57Q10, 05C38; 05C75 T Bıyıkoglu, Y Civan Annals of Combinatorics 16 (1), 37-56 , 2012 2012
MOST CITED SCHOLAR PUBLICATIONS
Vertex decomposable graphs, codismantlability, Cohen-Macaulayness and Castelnuovo-Mumford regularity T Biyikoglu, Y Civan arXiv preprint arXiv:1205.5631 , 2012 2012.0 Citations: 52
Homotopy decompositions and K-theory of Bott towers Y Civan, N Ray arXiv preprint math/0408261 , 2004 2004.0 Citations: 38
The v -number and Castelnuovo–Mumford regularity of graphs Y Civan Journal of Algebraic Combinatorics 57 (1), 161-169 , 2023 2023.0 Citations: 26
Linear colorings of simplicial complexes and collapsing Y Civan, E Yalçın Journal of Combinatorial Theory, Series A 114 (7), 1315-1331 , 2007 2007.0 Citations: 22
Castelnuovo-Mumford regularity of graphs T Biyikoglu, Y Civan arXiv preprint arXiv:1503.06018 , 2015 2015.0 Citations: 18
Bounding Castelnuovo-Mumford regularity of graphs via Lozin's transformation T Biyikoglu, Y Civan arXiv preprint arXiv:1302.3064 , 2013 2013.0 Citations: 12
Bott towers, crosspolytopes and torus actions Y Civan Geometriae Dedicata 113 (1), 55-74 , 2005 2005.0 Citations: 12
Upper maximal graphs of posets Y Civan Order 30 (2), 677-688 , 2013 2013.0 Citations: 7
Some examples in toric geometry Y Civan arXiv preprint math/0306029 , 2003 2003.0 Citations: 7
Bounding the chromatic number of squares of K4-minor-free graphs Y Civan, Z Deniz, MA Yetim Discrete Mathematics 342 (7), 1894-1903 , 2019 2019.0 Citations: 6
Homotopy decompositions and Y Civan, N Ray K, 1-33 , 0 Citations: 6
Four-cycled graphs with topological applications T Bıyıkoğlu, Y Civan Annals of Combinatorics 16 (1), 37-56 , 2012 2012.0 Citations: 5
Topology of families of toric manifolds Y Civan PQDT-Global , 2000 2000.0 Citations: 5
Coloring hypercomplete and hyperpath graphs Y Civan, D Taylan Turkish Journal of Mathematics 38 (1), 1-15 , 2014 2014.0 Citations: 3
Domination versus edge domination on claw-free graphs Y Civan, Z Deniz, MA Yetim Discrete Applied Mathematics 337, 171-172 , 2023 2023.0 Citations: 2
Projective dimension of (hyper) graphs and the Castelnuovo-Mumford regularity of bipartite graphs T Bıyıkoğlu, Y Civan arXiv preprint arXiv:1605.02956 , 2016 2016.0 Citations: 2
Open problems on linear Sperner families and lattices Y Civan Studia Scientiarum Mathematicarum Hungarica 45 (4), 563-568 , 2008 2008.0 Citations: 2
Chordal bipartite graphs, biclique vertex partitions and Castelnuovo-Mumford regularity of -subdivision graphs Y Civan, Z Deniz, O Duginov, MA Yetim arXiv preprint arXiv:2410.15213 , 2024 2024.0 Citations: 1
Gated independence in graphs Y Civan, Z Deniz, MA Yetim Discrete Applied Mathematics 353, 121-138 , 2024 2024.0 Citations: 1
Order-sensitive domination in partially ordered sets and graphs Y Civan, Z Deniz, MA Yetim Order 40 (1), 157-172 , 2023 2023.0 Citations: 1
