Graphes de cordes et espaces graphiques (Q795063)

Given a simple graph \(G=(V,E)\), let N(v) denote the set of vertices adjacent to a vertex v of V. The power set P(V) of V is a vector space on \(GF(2)=\{0,1\}\) if one defines \(xA=\emptyset\) for \(x=0\) and \(xA=A\) for \(x=1\), for any A in P(V). Any subspace of P(V) generated by a family of subsets of V of the form \((e(v)\{v\}+N(v),\quad v\in V)\) where e is an arbitrary mapping from V into GF(2), will be called a neighborhood space of G. A chord graph is a graph which is isomorphic to the graph of intersections of a set of chords in a circle. A space (X,F) where F is a subspace of P(X) is ''graphic'' if it is isomorphic to the space of cycles of a graph, and ''cographic'' if it is isomorphic to the space of cocycles of a graph. The essential result of the paper is that a space is graphic if and only if it is isomorphic to a space of neighborhoods of a chord graph. Several applications of this result are then considered. If \(G=(X,V)\) is a chord graph, if S is a nonempty stable set of G, different from V, then \((V,<w+N(w)\cap S,\quad w\in W)\) is graphic. Finally, several results concerning chain hypergraphs of a tree, graph planarity, bicycle spaces, interlacement graphs are shown to follow from the main theorem.