Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that for every connected graph G, the line graph of G has at most one more positive than negative adjacency eigenvalue; equivalently, the signature of a connected line graph is at most 1. We refute the conjecture with two independently found counterexamples: a 14-vertex cactus consisting of two pentagons attached by bridges to adjacent vertices of a square, whose line graph has inertia (9,0,7) by an exact characteristic-polynomial certificate, and a 48-vertex triangle-free graph found by simulated annealing and verified in exact rational arithmetic. Indeed, chaining copies of the 14-vertex graph yields connected graphs on 14k vertices whose line graphs have signature k+1 for every k>= 1. The signature of connected line graphs is therefore unbounded, and no constant-bound repair of the conjecture is possible.
The claw-free Schur-positivity conjecture, recorded by Stanley (1998) and credited there to Gasharov, asserts that the chromatic symmetric function of every claw-free graph is Schur-positive. We give a counterexample on 12 vertices: the line graph $G$ of the graph obtained from a 4-cycle by attaching triangles at two o...
We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pol...
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of M\"utze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by...
Sharma and Panda recently proved that every bipartite graph with a perfect matching has property (P); that is, it admits a non-singular real symmetric matrix with support graph G for which every vertex is a P -vertex. In this paper, we extend their result from bipartite graphs to arbitrary graphs. To this end, we intro...
Gupta and Iosevich introduced the edge complexity of a graph as the minimum Fourier ratio of its adjacency matrix over all vertex labelings and bounded it below by graph energy divided by the square root of twice the number of edges. We characterize equality for a fixed labeling: the Fourier transform of the adjacency...
Vishal Gupta, A. Iosevich, J. Iosevich et al.· 0 citations
Let $\mathcal{B}$ be the class consisting of the six-vertex bipartite graphs that possess a perfect matching and their complements. It is proved that every $\mathcal{B}$-free graph $G$ satisfies $\alpha(G)+\omega(G)\ge |V(G)|-1$. This establishes Conjecture 3.1 of Litjens, Polak and Sivaraman (B-Free Graphs Conjecture)...
Domenico Frijio· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
