The Topological Connectivity of the Independence Complex of Circular-Arc Graphs
Abstract
Let us denoted the topological connectivity of a simplicial complex $C$ plus 2 by $\eta(C)$. Let $\psi$ be a function from class of graphs to the set of positive integers together with $\infty$. Suppose $\psi$ satisfies the following properties: \newline $\psi{(K_{0})}$=0. \newline For every graph G there exists an edge $e=(x,y)$ of $G$ such that $$\psi{(G-e)}\geq{\psi{(G)}}$$ (where $G-e$ is obtained from $G$ by the removal of the edge $e$), and $$\psi{(G-N(\lbrace x,y \rbrace))}\geq{\psi{(G)}}-1$$ then $$\eta{(\mathcal{I}{(G)})}\geq\psi{(G)}$$ (where $(G-N(\lbrace x,y \rbrace))$ is obtained from $G$ by the removal of all neighbors of $x$ and $y$ (including, of course, $x$ and $y$ themselves). Let us denoted the maximal function satisfying the conditions above by $\psi_0$. Berger [3] prove the following conjecture: $$\eta{(\mathcal{I}{(G)})}=\psi_{0}{(G)}$$ for trees and completements of chordal graphs. Kawamura [2] proved conjecture, for chordal graphs. Berger [3] proved Conjecture for trees and completements of chordal graphs. In this article I proved the following theorem: Let $G$ be a circular-arc graph $G$ if $\psi_0(G)\leq 2$ then $\eta(\mathcal{I}(G))\leq 2$. Prior the attempt to verify the previously mentioned cases, we need a few preparations which will be discussed in the introduction.
Keywords
Topological connectivity,Independence Complex,Circular-Arc graphs
References
- [1] R. Aharoni, E. Berger, R. Ziv, Independent systems of representatives in weighted graphs, Combinatorica, 27 (2007), 253–267.
- [2] K. Kawamura, Independence complex of chordal graphs, Discrete Math., 310 (2010), 2204–2211.
- [3] E. Berger, Topological Methods in Matching Theory, Faculty Of Princeton University In Candidacy.
- [4] G. A. Dirac, On rigid circuit graphs, Math. sem. Univ. Hamburg, 25 (1961), 71-76 .
- [5] D. Kozov, Combinatorial Algebraic Topology.
