Partitioning graphs into complete and empty graphs |
| |
Authors: | T?naz Ekim |
| |
Institution: | a EPFL - FSB - IMA, Ecole Polytechnique Fédérale de Lausanne, CH 1015 Lausanne, Switzerland b Mathematics and Statistics, University of Alaska, Fairbanks, AK, 99775-6660, USA |
| |
Abstract: | Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs. |
| |
Keywords: | _method=retrieve& _eid=1-s2 0-S0012365X08003968& _mathId=si23 gif& _pii=S0012365X08003968& _issn=0012365X& _acct=C000053510& _version=1& _userid=1524097& md5=44b5509f269d8c9a2c278e985f6dd5b9')" style="cursor:pointer (j" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">(j k)-coloring Split graph Cocoloring |
本文献已被 ScienceDirect 等数据库收录! |
|