{"id":"arxiv/2603.26006","url":"https://arxiv.org/abs/2603.26006","tags":["cs.DM","math.CO"],"score":0,"title":"Computing fixed point free automorphisms of graphs","domain":"cs.DM","source":"arxiv","authors":["Aida Abiad","Gabriel Coutinho","Emanuel Juliano","Vinicius F. dos Santos","Sjanne Zeijlemaker"],"reviews":0,"subject":"cs.DM","summary":"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 G to itself. We revisit this problem and prove that FPFAut remains NP-complete when restricted to split, bipartite, k-subdivided, and H-free graphs, if H is not an induced subgraph of P_4. The class of P_4-free graphs receives the special name of cographs. We provide a polynomial time algorithm for three extensions of cographs: bounded modular-width graphs, tree-cographs and P_4-sparse graphs. Our approach uses…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-27","reactions":{}}