Maximal cliques in {P<inf>2</inf> ∪ P<inf>3</inf>,C<inf>4</inf>}-free graphs

We prove a decomposition theorem for the class G of P2∪P3,C4-free graphs. This theorem enables us to show that (i) every graph G in G has at most n+5 maximal cliques where n is the number of vertices in G, and (ii) for every G in G, χ(G)≤5ω(G)4⌉, where χ(G) (ω(G)) is the chromatic (clique) number of G. © 2010 Elsevier B.V. All rights reserved.