Signed analogs of bipartite graphs (Q1377721): Difference between revisions

Let \(\Sigma= (\Gamma,\sigma)\) be a finite signed graph (a graph with signed edges), where \(\Gamma= (V,E)\) is the underlying graph and \(\sigma: E\to\{+,-\}\) the sign labelling. Loops and multiple edges are allowed. The author proves, among other results, three equivalent statements and three equivalent properties of such \(\Sigma\) (Theorem 2). The sign of a walk \(W\) whose edge sequence is \(e_1,e_2,\dots, e_\ell\) is \(\sigma(W)= \sigma(e_1)\sigma(e_2)\cdots\sigma(e_\ell)\). \(\Sigma\) is bipartite if \(\Gamma\) is bipartite. A signed covering graph \(\Sigma\) is an unsigned graph whose vertex set is \(\widetilde V= \{+,-\}\times V\) and whose edge set \(\widetilde E\) consists of two edges with given properties for each \(e\in E\). By introducing a second edge signing \(\sigma_2\), that means \(\Sigma_2= (\Gamma,\sigma_2)\), the author obtains the doubly signed graph \((\Sigma,\sigma_2)\), and, among other things, he proves three equivalent statements for such \((\Sigma,\sigma_2)\) and three equivalent properties of them (Theorem 1). The investigations of the present paper may be summarized by the abstract of the author: We characterize the edge-signed graphs in which every ``significant'' positive closed walk (or combination of walks) has even length, under seven different criteria of significance, and also those edge-signed graphs whose double covering graph is bipartite. If the property of even length is generalized to positivity in a second edge signing, the characterizations generalize as well. We also characterize the edge-signed graphs with the smallest nontrivial chromatic numbers.