The gallai-younger conjecture for planar graphs |
| |
Authors: | B. A. Reed F. B. Shepherd |
| |
Affiliation: | (1) CNRS, Université Paris VI, Paris, France;(2) Centre for Discrete and Applicable Mathematics, LSE, London, U. K. |
| |
Abstract: | Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs. |
| |
Keywords: | 05 C 75 05 C 70 90 C 10 90 C 27 |
本文献已被 SpringerLink 等数据库收录! |
|