. "Partitions of graphs into cographs"@en . . "Gimbel, John" . . "278183" . "Cographs form the minimal family of graphs containing K-1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity; in particular, that computing the c-chromatic number is NP-complete for planar graphs."@en . "Partitions of graphs into cographs" . "1"^^ . . . "Cographs form the minimal family of graphs containing K-1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity; in particular, that computing the c-chromatic number is NP-complete for planar graphs." . "Partitions of graphs into cographs" . . . "P(1M0545), Z(MSM0021620838)" . "000284251900001" . "NL - Nizozemsko" . . "[531E233A157C]" . "9"^^ . . "11320" . "RIV/00216208:11320/10:10081040!RIV11-MSM-11320___" . . "Discrete Mathematics" . . "Ne\u0161et\u0159il, Jaroslav" . "310" . . "0012-365X" . "24" . . . "Partitions of graphs into cographs"@en . "RIV/00216208:11320/10:10081040" . . . "cographs; Partitions of graphs"@en . "2"^^ .