2013/08/28 by Nicolas Trotignon, Trotignon, Nicolas
Computer Science · Mathematics · #05Cxx #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1308.6139
openalex publication_date 2013/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A self-complementary graph is a graph isomorphic to its complement. An isomorphism between G and its complement, viewed as a permutation of V(G), is then called an antimorphism. A skew partition of G is a partition of V(G) into 4 sets A,B,C,D such that there is no edge between A,B and every possible edge between C,D. A symmetric partition of G is a partition of V(G) into 4 sets A,B,C,D such that there is no edge between A, D, no edge between B, C, every possible edge between A,B and every possible edge between C,D. We give a new proof of a theorem of Gibbs saying that every self-complementary graph on 4k vertices has k disjoint paths on 4 vertices as induced subgraph. This new proof gives more structural information than the original one. We conjecture that every self-complementary graph on 4k vertices either has an induced cycle on 5 vertices, or a skew partition, or a symmetric partition. The new proof of Gibb's theorem yields a proof of the conjecture for the self-complementary graphs that have an antimorphism that is the product of a two circular permutations, one of them of length 4.