Hubbry Logo
Orientation (graph theory)Orientation (graph theory)Main
Open search
Orientation (graph theory)
Community hub
Orientation (graph theory)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Orientation (graph theory)
Orientation (graph theory)
Orientation (graph theory)
View on Wikipedia
from Wikipedia
The directed graph (or digraph) on the right is an orientation of the undirected graph on the left.

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

Oriented graphs

[edit]

A directed graph is called an oriented graph if none of its pairs of vertices is linked by two mutually symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph).[1]

A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.[2] Sumner's conjecture states that every tournament with 2n − 2 vertices contains every polytree with n vertices.[3]

The number of non-isomorphic oriented graphs with n vertices (for n = 1, 2, 3, …) is

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (sequence A001174 in the OEIS).

Tournaments are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are bijective. Therefore, the same sequence of numbers also solves the graph enumeration problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.[4]

Constrained orientations

[edit]

A strong orientation is an orientation that results in a strongly connected graph. The closely related totally cyclic orientations are orientations in which every edge belongs to at least one simple cycle. An orientation of an undirected graph G is totally cyclic if and only if it is a strong orientation of every connected component of G. Robbins' theorem states that a graph has a strong orientation if and only if it is 2-edge-connected; disconnected graphs may have totally cyclic orientations, but only if they have no bridges.[5]

An acyclic orientation is an orientation that results in a directed acyclic graph. Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint. The Gallai–Hasse–Roy–Vitaver theorem states that a graph has an acyclic orientation in which the longest path has at most k vertices if and only if it can be colored with at most k colors.[6] Acyclic orientations and totally cyclic orientations are related to each other by planar duality. An acyclic orientation with a single source and a single sink is called a bipolar orientation.[7]

A transitive orientation is an orientation such that the resulting directed graph is its own transitive closure. The graphs with transitive orientations are called comparability graphs; they may be defined from a partially ordered set by making two elements adjacent whenever they are comparable in the partial order.[8] A transitive orientation, if one exists, can be found in linear time.[9] However, testing whether the resulting orientation (or any given orientation) is actually transitive requires more time, as it is equivalent in complexity to matrix multiplication.

An Eulerian orientation of an undirected graph is an orientation in which each vertex has equal in-degree and out-degree. Eulerian orientations of grid graphs arise in statistical mechanics in the theory of ice-type models.[10]

A Pfaffian orientation has the property that certain even-length cycles in the graph have an odd number of edges oriented in each of the two directions around the cycle. They always exist for planar graphs, but not for certain other graphs. They are used in the FKT algorithm for counting perfect matchings.[11]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Orientation (graph theory)

View on Grokipedia
from Grokipedia
In graph theory, an orientation of an undirected graph GG is a directed graph (digraph) obtained by assigning a direction to each edge of GG, such that every undirected edge {u,v}\{u, v\} becomes a directed arc either from uu to vv or from vv to uu. For a simple undirected graph with mm edges, there are exactly 2m2^m possible orientations, as each edge has two possible directions. An oriented graph specifically refers to an orientation of a simple undirected graph, which contains no loops or multiple arcs in the same direction. Orientations preserve the underlying undirected structure while introducing directionality, enabling the study of directed properties such as and cycles in digraphs. Key types include strong orientations, where the resulting digraph is strongly connected (i.e., there is a directed path between every pair of vertices); by Robbins' , a connected undirected graph admits a strong orientation if and only if it is 2-edge-connected. Acyclic orientations, which contain no directed cycles, are particularly significant, as their enumeration is tied to the graph's : the number of acyclic orientations of GG equals ∣χG(−1)∣|\chi_G(-1)|, where χG(λ)\chi_G(\lambda) is the chromatic polynomial of GG and nn is the number of vertices, with χG(−1)=(−1)n\chi_G(-1) = (-1)^n times that number. Special cases of orientations include tournaments, which are orientations of complete graphs where every pair of vertices is connected by exactly one directed arc; tournaments always contain a and have been extensively studied for properties like transitivity and score sequences. Graph orientation problems often seek orientations satisfying constraints, such as bounded out-degrees or acyclicity, with applications in network flow, scheduling, and .

Basic Concepts

Definition of Orientation

In graph theory, an orientation of an undirected graph GG is a obtained by assigning a unique direction to each undirected edge of GG, while preserving the vertex set and the incidences between vertices and edges. This process transforms the symmetric relationships in the undirected graph into asymmetric ones, without adding or removing any edges. Formally, if the undirected graph is denoted as G=(V,E)G = (V, E), where VV is the set of vertices and EE is the set of undirected edges, then an orientation is a D=(V,A)D = (V, A), where AA is a set of ordered pairs (u,v)(u, v) such that for each undirected edge {u,v}∈E\{u, v\} \in E, exactly one of (u,v)(u, v) or (v,u)(v, u) is in AA. This ensures that the underlying undirected graph of DD is precisely GG, and no bidirectional arcs (i.e., both (u,v)(u, v) and (v,u)(v, u)) are introduced unless the original graph had multiple edges, which is typically not the case in simple graphs. Unlike general directed graphs, which may include arbitrary arcs not derived from an undirected structure, orientations strictly originate from undirected graphs and assign directions only to existing edges, maintaining a one-to-one correspondence between the edge sets. A simple example is the P3P_3 on three vertices a,b,ca, b, c with edges {a,b}\{a, b\} and {b,c}\{b, c\}. One possible orientation directs both edges from left to right, yielding arcs (a,b)(a, b) and (b,c)(b, c); the other directs them from right to left, yielding (b,a)(b, a) and (c,b)(c, b).

Oriented Graphs

An oriented graph is a directed graph in which there are no symmetric pairs of directed edges, meaning that if there is an arc from vertex uu to vertex vv, then there is no arc from vv to uu (no 2-cycles). This structure arises naturally from assigning directions to the edges of an undirected graph without allowing bidirectional connections. Every orientation of an undirected graph produces an oriented graph, as the process assigns a single direction to each undirected edge, ensuring no symmetric arcs. However, not every directed graph is an oriented graph, since general directed graphs (digraphs) may include both directions between a pair of vertices. Prominent examples of oriented graphs include tournaments, which are orientations of the complete undirected graph KnK_n where every pair of distinct vertices is connected by exactly one directed edge. Another example is the , an acyclic oriented graph whose underlying undirected graph is a . The number of non-isomorphic oriented graphs on nn unlabeled vertices is given by the sequence 1 (for n=1n=1), 2 (for n=2n=2), 7 (for n=3n=3), 42 (for n=4n=4), and so on (OEIS A001174). A fundamental structural property of an oriented graph is its underlying undirected graph, obtained by ignoring the directions of all arcs, which is always a simple undirected graph without multiple edges or loops. Acyclic oriented graphs form an important subclass without directed cycles.

Fundamental Properties

Connectivity Properties

In , an orientation of an undirected graph is weakly connected the underlying undirected graph is connected. This property disregards the directions of and focuses solely on the existence of undirected paths between vertices. Weak connectivity is a fundamental prerequisite for studying more refined connectivity in oriented graphs, as it ensures the structure remains intact at the undirected level. A stronger notion is strong connectivity, where the oriented graph is strongly connected if there exists a directed path from every vertex to every other vertex. This requires that the orientation allows traversal in the directed sense across the entire graph, enabling full mutual . Strong connectivity is a key property in applications such as network flow and , where bidirectional access is essential. A basic implication of these properties is that in a weakly connected orientation, achieving strong connectivity is possible only if the underlying undirected graph has no bridges (i.e., it is 2-edge-connected). A bridge in the underlying graph would force any orientation of that edge to create a one-way cut, preventing directed paths across the separation in at least one direction. This condition is necessary and, by Robbins' theorem, also sufficient for the existence of a strong orientation. For example, orienting all edges of a cycle graph CnC_n (n≥3n \geq 3) in the same direction (e.g., clockwise) yields a strongly connected digraph, as it forms a directed Hamiltonian cycle allowing reachability between all vertices.

Degree Sequences in Orientations

In an orientation of an undirected graph G=(V,E)G = (V, E), each edge is assigned a unique direction, transforming GG into a directed graph where every vertex v∈Vv \in V has an in-degree d−(v)d^-(v), the number of edges directed toward vv, and an out-degree d+(v)d^+(v), the number of edges directed away from vv. The original degree satisfies the equation deg⁡G(v)=d−(v)+d+(v)\deg_G(v) = d^-(v) + d^+(v) for each vv, as each incident edge contributes to exactly one of the directed degrees. The out-degree sequence of the orientation is the ordered list (d+(v1),d+(v2),…,d+(vn))(d^+(v_1), d^+(v_2), \dots, d^+(v_n)), where n=∣V∣n = |V|, and similarly for the in-degree sequence. A necessary condition for a sequence (d1,d2,…,dn)(d_1, d_2, \dots, d_n) to be the out-degree sequence of some orientation of GG is that 0≤di≤deg⁡G(vi)0 \le d_i \le \deg_G(v_i) for each ii, reflecting the bounded choices for each vertex's outgoing edges, and that ∑i=1ndi=∣E∣\sum_{i=1}^n d_i = |E|, since each edge increases exactly one out-degree by 1. These conditions ensure consistency with the underlying structure but are not sufficient for realizability in general, as the specific connectivity and edge incidences in GG may prevent certain distributions. The problem of determining realizable out-degree sequences for orientations parallels the characterization of graphic sequences in undirected graphs (via the Erdős–Gállai theorem) but extends to directed settings with additional constraints from the fixed undirected skeleton. For instance, consider a dd- where every vertex has degree dd. Possible out-degrees for each vertex range from 0 to dd, subject to the sum condition. If dd is even, a balanced orientation exists where d+(v)=d/2d^+(v) = d/2 for all vv, corresponding to an Eulerian orientation with equal in- and out-degrees at every vertex; such an orientation can be constructed by finding an Eulerian tour in each connected component (possible since all degrees are even) and directing edges along the tour. This balanced case highlights how degree parity influences achievable sequences, with the total sum nd/2=∣E∣nd/2 = |E| naturally satisfied in regular graphs. A notable special case arises when GG is the complete graph KnK_n, where every orientation is a and degrees are n−1n-1 for all vertices. Here, the out-degree sequence is called a score sequence, and while the basic conditions hold, additional restrictions apply: by Landau's theorem, a non-decreasing s1≤s2≤⋯≤sns_1 \le s_2 \le \dots \le s_n with 0≤si≤n−10 \le s_i \le n-1 and ∑si=(n2)\sum s_i = \binom{n}{2} is realizable ∑i=1ksi≥(k2)\sum_{i=1}^k s_i \ge \binom{k}{2} for every k=1,…,n−1k = 1, \dots, n-1. This illustrates how global balance requirements beyond local bounds can preclude certain sequences, such as (0,0,3)(0, 0, 3) for n=3n=3, which fails the subset sum condition despite satisfying the bounds and total sum.

Special Types of Orientations

Strong Orientations

A strong orientation of an undirected graph is an assignment of directions to its edges such that the resulting is strongly connected, meaning there exists a directed path between every pair of vertices. , established in 1939, characterizes the graphs that admit strong orientations: an undirected graph has a strong orientation if and only if it is 2-edge-connected, that is, it remains connected after the removal of any single edge and thus contains no bridges. The theorem's proof proceeds by induction using ear decomposition, where a 2-edge-connected graph is built by starting with a cycle (which admits a strong orientation by directing edges consistently around it) and iteratively attaching an —a path with endpoints in the current subgraph and internal vertices new—to the structure, orienting the ear's edges to ensure paths exist in both directions between all vertices. This construction guarantees that the final orientation preserves strong connectivity throughout the decomposition. Strong orientations can be computed efficiently using a (DFS)-based algorithm on a 2-edge-connected graph. The method involves running DFS to produce a , orienting the edges away from the root to allow downward, and orienting the remaining back edges from descendants to ancestors in the to enable upward and close cycles appropriately. Since the absence of bridges ensures no dead ends in the DFS traversal, this orientation yields strong connectivity in linear time relative to the graph's size. For example, any cycle graph admits a strong orientation by directing all edges clockwise (or counterclockwise), forming a directed cycle where every vertex reaches every other. In contrast, a tree with more than one vertex, being replete with bridges, cannot admit a strong orientation, as the resulting digraph would have vertices with no incoming or outgoing paths to others beyond their subtrees.

Acyclic Orientations

An acyclic orientation of an undirected graph is an assignment of directions to its edges such that the resulting contains no directed cycles. This produces a (DAG), where every directed path has a finite length and no loops or circuits exist. A key property of acyclic orientations is the existence of a : a linear ordering of the vertices such that for every directed edge from vertex uu to vv, uu precedes vv in the ordering. Such orientations correspond to partial orders on the vertex set, where the directed edges represent the covering relations of the poset, and the defines the full order. Every undirected graph admits at least one acyclic orientation. One constructive method is to assign a to the vertices (e.g., labeling them from 1 to nn) and direct each edge from the lower-labeled endpoint to the higher-labeled one, ensuring no cycles form since labels increase along any path. For example, in a with partitions AA and BB, directing all edges from vertices in AA to those in BB yields an acyclic orientation, as paths alternate between partitions but cannot cycle back due to the one-way direction. The Gallai–Hasse–Roy–Vitaver characterizes the connection between acyclic orientations and : the chromatic number χ(G)\chi(G) of a graph GG equals the minimum, over all acyclic orientations of GG, of one plus the length of the longest directed path in that orientation. This minimum is achieved by some acyclic orientation, linking the theorem directly to proper vertex colorings where no path exceeds χ(G)−1\chi(G)-1 edges.

Eulerian Orientations

An Eulerian orientation of an undirected graph GG is an orientation of its edges such that, for every vertex vv, the in-degree equals the out-degree in the resulting . This condition implies that every vertex in GG must have even degree, as the degree of vv is the sum of its in-degree and out-degree, which must be even for balance. In the context of degree sequences for orientations, an Eulerian orientation requires the specific case where the prescribed in-degrees and out-degrees are equal at each vertex, summing to half the original degree. Such orientations exist if and only if GG has even degree at every vertex; this holds for both simple graphs and multigraphs, and extends to disconnected graphs provided each component satisfies the even-degree condition. For a connected graph with all even degrees (an Eulerian graph), an Eulerian orientation can be constructed by first finding an Eulerian circuit in GG and then orienting each edge in the direction of traversal along the circuit; this balances the degrees because the circuit enters and leaves each vertex equally often. Alternatively, constructions use edge-pairings at each vertex—pairing the incident edges into matching pairs and orienting each pair as one incoming and one outgoing edge—or model the problem as finding an integer circulation in a associated with zero demands at each vertex. In an Eulerian orientation, the resulting directed graph is balanced and, if strongly connected, admits a directed Eulerian circuit that traverses every arc exactly once. For example, consider the complete graph K3K_3, a triangle where each vertex has degree 2; orienting the edges in a cyclic manner (e.g., a→b→c→aa \to b \to c \to a) produces an Eulerian orientation with in-degree and out-degree 1 at each vertex, and the digraph is strongly connected with a directed Eulerian circuit.

Transitive Orientations

A transitive orientation of an undirected graph is an assignment of directions to its edges such that the resulting (digraph) is transitive: if there are directed edges u→vu \to v and v→wv \to w, then there must also be a directed edge u→wu \to w. Equivalently, the digraph equals its own , meaning no additional edges are needed to make all implied relations explicit. Such orientations are necessarily acyclic, as a directed cycle would imply contradictory or infinite edge requirements under transitivity. Graphs that admit a transitive orientation are known as comparability graphs, and they precisely correspond to the underlying undirected graphs of the directed graphs representing partial orders (posets), where edges indicate comparability between elements. In this context, the transitive orientation encodes the partial order, with directed edges representing the "less than" relation, and transitivity ensuring that the order is fully captured. This characterization links graph orientations directly to , where the comparability graph has an edge between two vertices if and only if they are comparable in the poset. Recognizing whether a graph admits a transitive orientation—and constructing one if it does—can be accomplished efficiently using algorithms that leverage modular decomposition, a structural partitioning of the graph into modules (subsets of vertices that behave uniformly with respect to the rest of the graph). A seminal linear-time algorithm by McConnell and Spinrad achieves this in O(n+m)O(n + m) time, where nn is the number of vertices and mm the number of edges, by first computing the modular decomposition and then orienting edges consistently within and between modules to ensure transitivity. Earlier works, such as those by Pnueli, Lempel, and Even, laid foundational algorithms for special cases like permutation graphs, but the general linear-time solution relies on these decomposition techniques. A classic example of a transitive orientation arises from a (linear order) on a set of elements, which orients the () as a transitive tournament: vertices are arranged in a chain, with every edge directed from earlier to later elements, ensuring all transitive edges are present and forming a linear without incomparabilities.

Pfaffian Orientations

In , a Pfaffian orientation of a graph GG is an assignment of directions to the edges such that the of the of the of the skew-symmetric AA (where entries are ±1\pm 1 based on the orientation and 0 otherwise) equals the number of perfect matchings in GG. This matrix encodes signed contributions from potential matchings, with the orientation ensuring that all perfect matchings receive consistent signs, while imperfect ones cancel out in the Pfaffian computation. The concept generalizes the permanent for bipartite graphs to non-bipartite cases via algebraic methods. Kasteleyn's theorem, established in 1967, asserts that every admits a Pfaffian orientation, thereby allowing the exact count of perfect matchings in polynomial time via the Fisher-Kasteleyn-Temperley (FKT) . This result resolves the dimer problem on planar lattices efficiently, with the computation serving as the core mechanism. The theorem applies specifically to s, including both bipartite and non-bipartite variants, though bipartite graphs benefit from simpler even-cycle conditions in their orientations. Key properties of Pfaffian orientations include the requirement that every even central cycle—meaning a cycle whose removal leaves a graph with a —must be oddly oriented, having an odd number of forward-directed edges in one traversal direction. This ensures signed enumerations where non-perfect matchings contribute zero net sign, isolating the perfect ones. For planar graphs, the orientation is Pfaffian if it makes all facial cycles oddly oriented relative to a fixed . To construct a Pfaffian orientation for a , orient the edges such that each bounded face has an odd number of clockwise-directed edges, which can be achieved by initially directing all edges clockwise around faces and flipping directions along cycles as needed to satisfy the oddness condition globally. This method extends to the outer face if the graph is embedded in the plane. A representative example is the m×nm \times n grid graph, where a staggered orientation—directing horizontal edges rightward on even rows and leftward on odd rows, with vertical edges upward—yields a Pfaffian orientation, enabling the of the associated matrix to compute the exact number of dimer coverings, equivalent to perfect matchings tiling the grid.

Applications and Extensions

In Order Theory and Coloring

Transitive orientations of undirected graphs provide a direct representation of partial orders (posets). Specifically, a graph admits a transitive orientation if and only if it is a comparability graph of a poset, where directed edges indicate the strict order relation between comparable elements, and the transitivity ensures that the order is preserved. In this context, the height of the poset, defined as the size of the longest chain minus one, equals the chromatic number of the comparability graph, as established by the Gallai–Hasse–Roy–Vitaver theorem. This theorem states that for any graph GG, the chromatic number χ(G)\chi(G) is equal to one plus the minimum length of the longest directed path over all acyclic orientations of GG. When restricted to transitive orientations, the longest path length precisely captures the poset height, linking graph coloring directly to order-theoretic properties. Comparability graphs, characterized by the existence of transitive orientations, form a subclass of perfect graphs, where χ(H)=ω(H)\chi(H) = \omega(H) (the clique number) for every induced subgraph HH. The transitive orientation not only aids in recognizing comparability graphs—via polynomial-time algorithms that construct such orientations—but also enables efficient coloring, as the poset structure allows partitioning into antichains corresponding to color classes, with the number of antichains equal to the height. These properties stem from foundational work in the 1960s, including algorithms for transitive orientations that exploit modular decompositions to verify and construct the ordering. Dilworth's theorem further illustrates the role of orientations in , asserting that in any finite poset, the size of the maximum equals the minimum number of required to cover the poset. Given a transitive orientation representing the poset as a (DAG), this equality can be computed algorithmically by reducing the minimum chain cover to a minimum path cover in the DAG, which is equivalent to nn minus the size of a maximum matching in a associated constructed by splitting vertices into in- and out-parts. Thus, orientations transform the poset into a graph-theoretic problem solvable via network flow techniques, providing a practical method to quantify sizes and chain decompositions. Beyond transitive cases, acyclic orientations yield upper bounds on the chromatic number via the Gallai–Hasse–Roy–Vitaver theorem, where χ(G)≤1+ℓ(D)\chi(G) \leq 1 + \ell(D) for any acyclic orientation DD, with ℓ(D)\ell(D) the longest path length, and equality achievable by an optimal orientation. These connections, developed in the and 1960s by researchers including Gallai, , Hasse, and Vitaver, underscore the interplay between orientations, posets, and coloring, influencing subsequent advancements in algorithmic and perfect graph recognition.

In Matching and Enumeration

The Fisher-Kasteleyn-Temperley (FKT) algorithm employs orientations to enable the exact enumeration of perfect matchings in planar graphs. In this approach, a orientation ensures that the signed sum over all perfect matchings, computed as the of a corresponding skew-symmetric adjacency matrix, has all positive signs, so its square equals the total number of perfect matchings. The itself is obtained via on the matrix, achieving a of O(n^3) for a graph with n vertices. In , orientations facilitate the modeling and exact computation of partition functions for lattice systems. For dimer models, where configurations correspond to perfect matchings covering the lattice sites, orientations allow the partition function to be expressed as the square of a , as applied to the . Similarly, for the on planar graphs without external fields, the partition function can be represented using Pfaffians derived from orientations of an associated doubled graph, enabling exact solutions via similar matrix methods. Orientations also connect to broader enumeration problems, such as counting acyclic orientations, which equals the absolute value of the evaluated at -1. For the K_n, this yields exactly n! acyclic orientations, each corresponding to a transitive induced by a linear ordering of the vertices. An extension of the matrix-tree theorem to directed graphs counts arborescences—rooted spanning trees oriented toward a fixed root—via the of a principal minor of the directed . As a concrete example, orientations of grid graphs enumerate domino tilings, where each tiling is a ; for an m-by-n grid, the exact count is given by the product over Fourier modes in Kasteleyn's formulation, demonstrating the method's power for lattice enumerations.

Open Problems

One of the longstanding open problems in the theory of graph orientations is Sumner's universal , proposed in the , which states that every on 2n−22n-2 vertices contains a copy of every oriented on nn vertices. This implies that tournaments are universal containers for oriented trees, with significant implications for and the structure of directed graphs. Although the full remains unresolved as of 2025, substantial progress has been made using probabilistic methods; for instance, it has been proven for all sufficiently large tournaments, where the order exceeds some function of nn. More recent partial results, such as those establishing the for trees with many leaves, rely on random constructions but fall short of a complete proof. Another major open question concerns Pfaffian orientations, specifically characterizing which general graphs admit such an orientation—where the Pfaffian counts perfect matchings efficiently via the determinant of the skew-adjacency matrix. While all planar graphs are known to be Pfaffian, the problem for non-planar graphs is resolved only for certain classes, such as bipartite graphs and some claw-free graphs, leaving the general case open. Moreover, the computational complexity of determining whether a given graph has a Pfaffian orientation remains unresolved, with no polynomial-time algorithm known despite extensive study. In the realm of strong orientations, the complexity of finding an orientation that achieves strong connectivity while minimizing the size of a (to ensure acyclicity in the reverse) poses significant challenges, particularly in approximating optimal solutions for dense or bounded-degree graphs. Open questions include precise approximation ratios for feedback arc set decompositions in oriented graphs, such as determining whether the ratio \fasd(Δ,g)=g\fasd(\Delta, g) = g holds for fixed maximum out-degree Δ≥3\Delta \geq 3 and large gg, with exact values elusive even for small parameters like Δ=3,g=6\Delta = 3, g = 6.

References

  1. https://www.cs.rpi.edu/~slotag/classes/SU19/slides/lec04.pdf
  2. http://match.stanford.edu/reference/graphs/sage/graphs/orientations.html
  3. https://math.vanderbilt.edu/ellingmn/6710/basiccon2.pdf
  4. https://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Morgenstern.pdf
  5. https://courses.grainger.illinois.edu/cs598csc/sp2010/Lectures/Lecture24.pdf
  6. https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf
  7. https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1375&context=cstech
  8. https://mathworld.wolfram.com/GraphOrientation.html
  9. https://mathworld.wolfram.com/OrientedGraph.html
  10. https://encyclopediaofmath.org/wiki/Graph%2C_oriented
  11. https://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf
  12. https://oeis.org/A001174
  13. https://mc.sbm.org.br/wp-content/uploads/sites/9/sites/9/2021/12/39-19.pdf
  14. https://diestel-graph-theory.com/basic.html
  15. https://www.cs.rpi.edu/~slotag/classes/SP24t/notes/lec05.pdf
  16. https://www.sciencedirect.com/science/article/pii/S0195669817300409
  17. https://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p19.pdf
  18. https://www.zib.de/userpage/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf
  19. https://math.mit.edu/~goemans/18438F09/lec16.pdf
  20. https://onlinelibrary.wiley.com/doi/full/10.1111/itor.13229
  21. https://cp-algorithms.com/graph/strong-orientation.html
  22. https://page.mi.fu-berlin.de/rote/Papers/pdf/Acyclic%2Borientation%2Bof%2Bdrawings.pdf
  23. https://www.sciencedirect.com/science/article/pii/S0196885898905954
  24. https://www.geeksforgeeks.org/dsa/topological-sorting/
  25. http://dspace.mit.edu/bitstream/handle/1721.1/99325/923259848-MIT.pdf?sequence=1
  26. http://www.math.tau.ac.il/~krivelev/teaching/co22/LectureNotes.pdf
  27. https://arxiv.org/pdf/2303.09021
  28. https://people.cs.uchicago.edu/~laci/papers/eulerian-soda06.pdf
  29. https://egres.elte.hu/tr/egres-06-01.pdf
  30. https://epubs.siam.org/doi/10.1137/0606065
  31. https://www.cs.colostate.edu/~rmm/linTOSODA.pdf
  32. https://www.sciencedirect.com/science/article/pii/S0166218X15003868
  33. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/C9E11C37FE3FCB7A88C333E74C9EED01/S0008414X00053074a.pdf/transitive_orientation_of_graphs_and_identification_of_permutation_graphs.pdf
  34. https://www.combinatorics.org/ojs/index.php/eljc/article/download/v6i1r6/pdf/
  35. https://thomas.math.gatech.edu/PAP/pfafsurv.pdf
  36. https://www.numdam.org/item/M2AN_1967__1_5_129_0.pdf
  37. https://dwest.web.illinois.edu/pubs/graphord.pdf
  38. https://www.sciencedirect.com/science/article/pii/S0012365X98003197
  39. https://www.math.ucsd.edu/~asuk/dilworth.pdf
  40. https://www.mscs.dal.ca/~janssen/4115/presentations/Kyle.pdf
  41. https://www.tandfonline.com/doi/abs/10.1080/14786436108243366
  42. https://www.sciencedirect.com/science/article/pii/0012365X73901088
  43. https://arxiv.org/abs/1010.4430
  44. https://ics.uci.edu/~vazirani/VY-Pfaff.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.