Some extremal results in cochromatic and dichromatic theory |
| |
Authors: | Paul Erds John Gimbel Dieter Kratsch |
| |
Institution: | Paul Erdös,John Gimbel,Dieter Kratsch |
| |
Abstract: | For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {Gn} is a family of graphs where Gn has o(n2 log2(n)) edges, then z(Gn) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m2 ln2(m)). |
| |
Keywords: | |
|
|