13 papers
Tightness of a MaxCut Lower Bound via Vector Chromatic Number
Emanuel Juliano
Recently, Balla, Janzer, and Sudakov showed a lower bound on the MaxCut in terms of the vector chromatic number, recovering known results on the MaxCut of -free graphs. In this…
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…
The edge-isoperimetric number of graphs and their powers
Aida Abiad, Nils van de Berg, Emanuel Juliano +4
We obtain several sharp spectral bounds, approximations, and exact values for the isoperimetric number and related edge-expansion parameters of graphs. Our results focus on graph p…
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…
On the zero-free region for the chromatic polynomial of graphs with maximum degree and girth
Paula M. S. Fialho, Emanuel Juliano, Aldo Procacci
The purpose of the present paper is to provide, for all pairs of integers with $\D\ge 3$ and , a positive number such that chromatic polynomial o…
A remark on the Whitney Broken Circuit Theorem
Paula M. S. Fialho, Emanuel Juliano, Aldo Procacci
In the present note we show, via the connection between chromatic polynomial and Potts model, that the Whitney Broken circuit theorem is in fact a special case of a more general id…
Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins +1
A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matc…
Forbidden subdivision in integral trees
Emanuel Juliano
We show that if all the eigenvalues of a tree are integers, then it does not contain a subdivided edge with 7 vertices.
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…
No perfect state transfer in trees with more than 3 vertices
Gabriel Coutinho, Emanuel Juliano, Thomás Jung Spier
We prove that the only trees that admit perfect state transfer according to the adjacency matrix model are and . This answers a question first asked by Godsil in 2012 an…
The spectrum of symmetric decorated paths
Gabriel Coutinho, Emanuel Juliano, Thomás Jung Spier
The main result of this paper states that in a rooted product of a path with rooted graphs which are disposed in a somewhat mirror-symmetric fashion, there are distinct eigenvalues…
Strong cospectrality in trees
Gabriel Coutinho, Emanuel Juliano, Thomás Jung Spier
We prove that no tree contains a set of three vertices which are pairwise strongly cospectral. This answers a question raised by Godsil and Smith in 2017.
Quantum walks do not like bridges
Gabriel Coutinho, Chris Godsil, Emanuel Juliano +1
We consider graphs with two cut vertices joined by a path with one or two edges, and prove that there can be no quantum perfect state transfer between these vertices, unless the gr…