On Graphs Which Have Locally Complete 2‐Edge‐colourings and Their Relationship to Proper Circular‐Arc Graphs

ABSTRACT A 2‐edge‐coloured graph is called locally complete if for each vertex , the vertices adjacent to through edges of the same colour induce a complete subgraph in . Locally complete 2‐edge‐coloured graphs have nice properties, and there exists a polynomial algorithm to decide whether such a graph has an alternating hamiltonian cycle, where alternating means that the colour of two consecutive edges on the cycle are different. Graphs which have locally complete 2‐edge colourings are one of two types of claw‐free perfect graphs indecomposable via clique‐cutsets. In this paper, we characterize the graphs which have locally complete 2‐edge‐colourings by a forbidden substructure, analogous to the one given by Gallai for cocomparability graphs. Our characterization implies a polynomial time recognition algorithm for this class of graphs. We compare the graphs which have locally complete 2‐edge‐colourings with proper interval graphs and proper circular‐arc graphs (which are the graphs having local tournament orientations). We characterize proper interval graphs and proper circular‐arc graphs which have locally complete 2‐edge‐colourings by forbidden subgraphs.