Showing 2026Show all
3 papers · 1 filter
math.CO2026
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…
math.CO2026
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…
cs.DM2026
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…