2018/08/03 by Ratko Darda, Martin Milanič, Darda, Ratko +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1808.01313
openalex publication_date 2018/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is square-complementary (squco, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is an induced subgraph of a squco bipartite graph, that the problem of recognizing squco graphs is graph isomorphism complete, and that no nontrivial squco graph is both bipartite and planar. These results resolve three of the open problems posed in Discrete Math. 327 (2014) 62-75.