Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

A combinatorial decomposition of acyclic simplicial complexes

It is proved that if Δ is a finite acyclic simplicial complex, then there is a subcomplex Δ′ Δ and a bijection η: Δ′ → Δ − Δ′ such that F η(F) and |η(F)−F|=1 for all F Δ′. This improves an earlier result of Kalai. An immediate corollary is a characterization (first due to Kalai) of the f-vector of an acyclic simplicial complex. Several generalizations, some proved and some conjectured, are discussed.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Nearly acyclic graphs are reconstructible

We prove that a graph G is reconstructible if G has a node v with G-v acyclic. The proof uses colored graphs and shows how to reconstruct some graphs from pieces which share a common subgraph having few automorphisms.     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006     

On acyclic colorings of planar graphs

The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper.     

On acyclic colorings of planar graphs

The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper.     

A decomposition property of polyhedra

A polyhedronP = {x∈ ℝ ₊ ⁿ ∣d ⩽Ax ⩽e} is said to have the real decomposition property (RDP) if for any positiveT and any realx∈TP, there are positive coefficients λ₁,…, λ _r and integers ¹, …,s ^r ∈P withx = λ _l s ^l + … + λ _r s ^r andT=λ _l + ⋯ + λ _r . We give a constructive proof that this property holds for a polyhedronP iffP is integral. This construction is used to show that some classes of polyhedra have an integral decomposition property. Furthemore, the RDP provides a generalization of the theorem of Birkhoff-von Neumann. So RDP may be used in some scheduling problems on parallel processors with preemptions.     

Cost-minimal trees in directed acyclic graphs

Summary A number of examples are given where one seeks a minimal-cost tree to span a given subset of the nodes of a connected, directed, acyclic graph (we call such a graph monotonic). Some of these examples require an algorithm to transform the problem into the form of a minimization problem in a monotonic graph; this algorithm is also given. Finally, an implicit enumeration algorithm is presented for finding the cost-minimal tree of the graph, which spans the designated subset of the nodes, and some computational results are given.

---

Zusammenfassung Es werden Beispiele aufgezeigt, bei denen ein kostenminimaler Baum gesucht wird, der eine gegebene Untermenge von Knoten in einem verbundenen, gerichteten und azyklischen Graphen aufspannt. Ein solcher Graph wird hier als monotoner Graph bezeichnet. Einige dieser Beispiele erfordern einen Algorithmus, der das gegebene Problem in eine Minimierungsaufgabe in einem monotonen Graphen überträgt. Dieser Algorithmus zur Konstruktion des Graphen wird formuliert. Schließlich wird ein spezialisiertes implizites Enumerationsverfahren vorgestellt, das den kostenminimalen Baum zu der gegebenen Untermenge von Knoten in dem vorliegenden monotonen Graphen konstruiert. Rechenerfahrungen bilden den Abschluß.

     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

A decomposition for strongly perfect graphs

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H. We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, E) is a partition of V into nonempty disjoint subsets V₁, V₂ such that in every P₄ with vertices in both V_iapos;s, each of the three edges has an endpoint in V₁ and the other in V₂. We give a good characterization of graphs that admit a stitch decomposition and establish several results concerning the stitch decomposition of strongly perfect graphs.     

On acyclic colorings of graphs on surfaces

A properk-coloring of a graph is acyclic if every 2-chromatic subgraph is acyclic. Borodin showed that every planar graph has an acyclic 5-coloring. This paper shows that the acyclic chromatic number of the projective plane is at most 7. The acyclic chromatic number of an arbitrary surface with Euler characteristic η=−γ is at mostO(γ^4/7). This is nearly tight; for every γ>0 there are graphs embeddable on surfaces of Euler characteristic −γ whose acyclic chromatic number is at least Ω(γ^4/7/(logγ)^1/7). Therefore, the conjecture of Borodin that the acyclic chromatic number of any surface but the plane is the same as its chromatic number is false for all surfaces with large γ (and may very well be false for all surfaces). This author's research was supported in part by a United States Israeli BSF grant. This author's research was supported by the Ministry of Research and Technology of Slovenia, Research Project P1-0210-101-92. This author's research was supported by the Office of Naval Research, grant number N00014-92-J-1965.     

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.     

A note on acyclic domination number in graphs of diameter two

A subset S of the vertex set of a graph G is called acyclic if the subgraph it induces in G contains no cycles. S is called an acyclic dominating set of G if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by γ_a(G), is called the acyclic domination number of G. Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151-165] introduced the concept of acyclic domination and posed the following open problem: if δ(G) is the minimum degree of G, is γ_a(G)?δ(G) for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive k, there is a graph G with diameter two such that γ_a(G)-δ(G)?k.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

A note on the acyclic 3-choosability of some planar graphs

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is said to be acyclically k-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable.     

Tree decomposition of graphs

Let H be a tree on h≥2 vertices. It is shown that if G=(V, E) is a graph with \delta (G)\ge (|V|/2)+10h^4\sqrt{|V|\log|V|} , and h−1 divides |E|, then there is a decomposition of the edges of G into copies of H. This result is asymptotically the best possible for all trees with at least three vertices. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 237–251, 1998     

Frugal, acyclic and star colourings of graphs

Given a graph G=(V,E), a vertex colouring of V is t-frugal if no colour appears more than t times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind et al. (1997) [14] studied proper t-frugal colourings and Yuster (1998) [22] studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study.     

Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.