×

Planar digraphs without large acyclic sets. (English) Zbl 1365.05111

Summary: 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\geq q\geq3\), there exist oriented planar graphs of order \(n\) and digirth \(g\) for which the size of the maximum acyclic set is at most \(\lceil\frac{n(g-2)+1}{g-1}\rceil\). When \(g=3\) this result disproves a conjecture of A. Harutyunyan [Brooks-type results for coloring of digraphs. Burnaby, BC: Simon Fraser University (PhD Thesis) (2011)] and shows that a question of M. O. Albertson is best possible.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C10 Planar graphs; geometric and topological aspects of graph theory

Software:

SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albertson, Graph Theory and Related Topics (1979)
[2] Borodin, A proof of Grünbaum’s conjecture on the acyclic 5-colorability of planar graphs (in Russian), Doklady Akademii Nauk SSSR 231 (1) pp 18– (1976)
[3] A. Harutyunyan Brooks-type results for coloring of digraphs
[4] Harutyunyan, Planar digraphs of digirth 5 are 2-colorable, J Graph Theory (2015) · Zbl 1359.05052
[5] Golowich, Acyclic subgraphs of planar digraphs, Electronic J Combin 22 (3) (2015) · Zbl 1325.05060
[6] B. Mohar Acyclic partitions of planar digraphs, Problem of the Month July 2002 http://www.fmf.uni-lj.si/ mohar/Problems/P0207AcyclicPartitions.html
[7] V. Neumann-Lara Vertex colourings in digraphs, Some Problems 1985
[8] The Sage Development Team Sage Mathematics Software (Version 6.3) 2014 http://www.sagemath.org
[9] Tait, Listing’s topologie, Lond Edinb Dublin Philos Mag J Sci V. Series 17 pp 30– (1884)
[10] Tutte, On Hamiltonian circuits, J Lond Math Soc 21 pp 98– (1964) · Zbl 0061.41306
[11] D. B. West Induced Acyclic Subgraphs in Planar Digraphs http://www.math.illinois.edu/dwest/regs/plandifor.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.