4 papers
A Lovász Theta Parameter and Theta Body for Signed Graphs
Gabriel Coutinho
We introduce a Lovász-type semidefinite parameter for balanced colouring of signed graphs. Its homomorphism target is a unit sphere equipped with an orthogonal involution: the fix…
Computing fixed point free automorphisms of graphs
Aida Abiad, Gabriel Coutinho, Emanuel Juliano +2
In 1981, Lubiw proved that the fixed point free automorphism problem (FPFAut) is NP-complete: given a graph G, determine whether there exists an automorphism that maps no vertex of…
A graph energy conjecture through the lenses of semidefinite programming
Aida Abiad, Gabriel Coutinho, Emanuel Juliano +1
Let be a graph on vertices with independence number . Let be the energy of a graph, defined as the sum of the absolute values of the adjacency eigen…
Conic programming to understand sums of squares of eigenvalues of graphs
Gabriel Coutinho, Thomás Jung Spier, Shengtong Zhang
In this paper we prove a conjecture by Wocjan, Elphick and Anekstein (2018) which upper bounds the sum of the squares of the positive (or negative) eigenvalues of the adjacency mat…