Premium
Planar Digraphs without Large Acyclic Sets
Author(s) -
Knauer Kolja,
Valicov Petru,
Wenger Paul S.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22061
Subject(s) - directed acyclic graph , combinatorics , feedback arc set , mathematics , directed graph , conjecture , planar graph , set (abstract data type) , discrete mathematics , graph , planar , computer science , line graph , computer graphics (images) , voltage graph , programming language
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 n ≥ g ≥ 3 , there exist oriented planar graphs of order n and digirth g for which the size of the maximum acyclic set is at most ⌈ n ( g − 2 ) + 1 g − 1 ⌉ . When g = 3 this result disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.