Originators: Terry McKee (presented by D.B. West - REGS 2009)
Definitions/Background: A graph is chordal if every cycle (of length at least 4) has a chord. Chordal graphs originally were called triangulated graphs. A chord joining vertices that have distance 2 along a cycle is a triangular chord of the cycle. It is easy to prove that a graph is chordal if and only if every cycle has a triangular chord, which in turn is equivalent to every cycle being the binary sum of a cycle with one less edge and a triangle. Given this, a k-cycle is the binary sum of k-2 triangles. Jamison [J] proved that the converse also holds, so that a graph is chordal if and only if every cycle C is the binary sum of |V(C)|-2 triangles.
McKee [M] has generalized these notions. In particular, he defines a pentagulated graph (or pentangulated graph) to be a graph in which every cycle C of length at least 5 is the binary sum of |V(C)|-4 cycles of length 5. A graph is incrementally pentagulated if every cycle C of length at least 6 is the binary sum of a cycle C' with one less edge and a 5-cycle. Note that such a 5-cycle must consist of two crossing chords of C and three edges along C. By the same reasoning as for chordal graphs, every incrementally pentagulated graph is pentagulated. McKee's conjecture is that the converse holds.
Conjecture: A graph is pentagulated if and only if it is incrementally pentagulated.
Comments: For example, the graph consisting of the 7-cycle [v1,...,v7] plus the three chords {v1v4, v2v6, v4v7} satisfies both properties.
References:
[J] Jamison, Robert E.
On the null-homotopy of bridged graphs.
European J. Combin. 8 (1987), no. 4, 421--428.
[M] McKee, Terry.
Analogies between pentangulated and triangulated graphs,
presentation at 2nd CanaDAM conference, Montreal, 2009.