Fast recognition of doubled graphs

Double split graphs form one of the five basic classes in the proof of the strong perfect graph theorem by Chudnovsky et al. [3]. A doubled graph is any induced subgraph of a double split graph. We show here that deciding if a graph G   is a doubled graph can be done in time O(|V(G)|+|E(G)|)O(|V(G)|+|E(G)|) by analyzing the degree structure of the graph.