Partitions of Graphs into Cographs

摘要: Abstract Cographs from the minimal family of graphs containing K 1 which are closed with respect to complements and unions. We discuss vertex partitions into smallest number cographs, where partition is as small possible. shall call order such a c-chromatic graph. begin by axiomatizing several well-known graphical parameters motivation for this function. present bounds on in terms expressions. show that if graph triangle-free, then its chromatic bounded between twice number. both sharp, arbitrarily high girth. This provides an alternative proof result [3]; there exist triangle-free large numbers. any planar girth at least 11 has most two. close remarks computational complexity. In particular, we computing NP-complete graphs.