6 papers
On some k-fold generalizations of Lovász theta and their sandwich theorems
Marcel K Carli Silva, Gabriel Coutinho, Thiago Oliveira +1
We study several -fold generalizations of the Lovász theta function associated with the maximum -colorable induced subgraph problem. The first is the Narasimhan--Manber param…
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 fixe…
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 eigenv…
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…
Spectral upper bounds for the Grundy number of a graph
Thiago Assis, Gabriel Coutinho, Emanuel Juliano
The Grundy number of a graph is the minimum number of colors needed to properly color the graph using the first-fit greedy algorithm regardless of the initial vertex ordering. Comp…