Logo image
Se connecter
Planar Digraphs without Large Acyclic Sets
Article de revue   Avec comité de lecture

Planar Digraphs without Large Acyclic Sets

Kolja Knauer, Petru Valicov et Paul S. Wenger
Journal of graph theory, Vol.85(1), pp.288-291
01/05/2017

Résumé

Mathematics Physical Sciences Science & Technology
Given a directed graph, an acyclic set is a set of vertices inducing a directed subgraph with no directed cycle. In this note, we show that for all integers ng3, there exist oriented planar graphs of order n and digirth g for which the size of the maximum acyclic set is at most remvoe<n(g-2)+1g-1. When g=3 this result disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible. (C) 2016 Wiley Periodicals, Inc.

Indicateurs

1 Consultations de la notice

Détails

Logo image