User Tools

Site Tools


Nicholas Lacasse (Binghamton)

Signed Graphs and Negative Bipartizability

Abstract for the Combinatorics Seminar 2019 December 3

A signed graph Σ = (Γ, σ) is a graph Γ with a sign function σ: E(Γ) → {−1, +1}. Using these edge signs, we may give any circle in Σ a sign by declaring the sign of the circle to be the product of the signs of its edges. We call Σ balanced if every circle is positive. If Σ is not balanced, we may select some subset N in E(Σ) and negate (change the sign of) every edge in N. If doing this gives a balanced graph, we call N a negation set of Σ. Packing sets of a certain kind means finding disjoint sets of that kind. In studying the packing of negation sets, bipartite negation sets play an important role. Unfortunately, for a given signed graph, it is not known how to find a bipartite negation set for it or if it even has one. I will focus on two results: the first shows us how, for a certain class of signed graphs, we may obtain a bipartite negation set and the second will prove a different class of signed graphs all have bipartite negation sets.

seminars/comb/abstract.201912lac.txt · Last modified: 2020/01/29 14:03 (external edit)