Some extremal results in cochromatic and dichromatic theory

✍ Scribed by Paul Erdös; John Gimbel; Dieter Kratsch

• Publisher: John Wiley and Sons
• Year: 1991
• Tongue: English
• Weight: 289 KB
• Volume: 15
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190150604

✦ Synopsis

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 {G~n~} is a family of graphs where G~n~ has o(n^2^ log^2^(n)) edges, then z(G~n~) = 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) = θ(m^2^ ln^2^(m)).