×

On maximal clique irreducible graphs. (English) Zbl 0735.05052

Summary: A graph \(G\) is said to be maximal clique irreducible if each maximal clique in \(G\) contains an edge which is not contained in any other maximal clique of \(G\). In 1981, Opsut and Roberts proved that any interval graph is maximal clique irreducible. We generalize their result and consider the question of characterizing maximal clique irreducible graphs.

MSC:

05C35 Extremal problems in graph theory
PDF BibTeX XML Cite