Searching for acyclic orientations of graphs
type: Item
instance of: scholarly article
title: Searching for acyclic orientations of graphs
zbMATH Open document ID: 0831.05033
DOI: 10.1016/0012-365X(94)00281-M
author: Martin Aigner
author: Eberhard Triesch
author: Zsolt Tuza
published in: Discrete Mathematics
publication date: 1996-02-12T00:00:00Z
review text: For an undirected graph \(G\), \(c(G)\) is defined to be the minimum integer \(k\) with the property that there exists a subgraph \(H\) of \(G\) with \(k\) edges such that, no matter how \(H\) is acyclically oriented, this orientation can be extended uniquely to an acyclic orientation of all edges of \(G\). The number of acyclic orientations of \(G\) is denoted by \(a (G)\); the maximum number of independent vertices is denoted by \(\alpha (G)\). A graph \(G \) is exhaustive if \(c(G) = |E (G) |\). Theorem 2. For all graphs \(G\) on \(n\) vertices, \[ n \log_2 {n \over \alpha (G)} - n \log_2e+ {1 \over 2} (2 + \log_2n) < c(G) < \alpha (G) n \left (\log_2 {n \over \alpha (G)} + 1 \right). \] This permits an answer to an orally communicated question of P. Erdös: Corollary 3. If \((\begin{smallmatrix} n \\ 2 \end{smallmatrix}) - |E(G) |= o(n^2)\), then \(c(G) = o(n^2)\) as \(n \to \infty\). For every \(0 < \varepsilon < {1 \over 2}\) there is a \(\delta > 0\) such that, for large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(({1 \over 2} - \varepsilon) n^2\) edges, satisfying \(c(G) \geq \delta n^2\). A theorem of \textit{J. Nešetřil} and \textit{V. Rödl} [On a probabilistic graph-theoretical method, Proc. Am. Math. Soc. 72, 417-421 (1978; Zbl 0399.05007)] is generalized: Theorem 8. For each natural number \(s\), there exists a nonexhaustive graph with girth at least \(s\). The authors acknowledge that N. Alon and Zs. Tuza have proved that the line graphs of cubic triangle-free graphs need not be exhaustive. The size of an exhaustive graph is bounded: Theorem 10. (i) For all \(n \geq 6\), the number of edges in an exhaustive graph on \(n\) vertices is at most \(\lfloor {n^2 \over 4} \rfloor\). (ii) For all \(n \geq 7\), the complete bipartite graph \(K_{\lfloor {n \over 2}\rfloor, \lfloor {n \over 2} \rfloor}\) is the only exhaustive graph with \(\lfloor {n^2 \over 4} \rfloor\) edges. The paper concludes with two open problems: What is the complex…
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 797068
zbMATH Keywords: orientation
zbMATH Keywords: acyclic
zbMATH Keywords: independent vertices
zbMATH Keywords: exhaustive graph
zbMATH Keywords: problems
zbMATH Keywords: complexity
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Q3994535
cites work: Q3682518
cites work: Q3883524
cites work: Q3283482
cites work: Parallel concepts in graph theory
cites work: Q3706485
cites work: Hard Enumeration Problems in Geometry and Combinatorics
cites work: On a Probabilistic Graph-Theoretical Method
cites work: Q3726174
cites work: Acyclic orientations of graphs
description: scientific article; zbMATH DE number 797068