Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-16T16:14:42.796Z Has data issue: false hasContentIssue false

Splitting digraphs

Published online by Cambridge University Press:  04 September 2006

NOGA ALON
Affiliation:
Tel Aviv University, Tel Aviv 69978, Israel and IAS, Princeton, NJ 08540, [email protected]

Abstract

There are several known results asserting that undirected graphs can be partitioned in a way that satisfies various constraints imposed on the degrees. The corresponding results for directed graphs, where degrees are replaced by outdegrees, often fail, and when they do hold, they are usually much harder, and lead to fascinating open problems. In this note we list three problems of this type, and mention the undirected analogues. All graphs and digraphs considered here are simple, that is, they have no loops and no multiple edges.

Type
PROBLEM SECTION
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)