pith. sign in

arxiv: 2502.21287 · v2 · pith:IIPPTMIJnew · submitted 2025-02-28 · 🧮 math.CO

Orientations of graphs omitting non-edge-critical directed graphs

classification 🧮 math.CO
keywords graphsdirectedexactgaveanswerbounddenotefurther
0
0 comments X
read the original abstract

In 1974, Erd\H{o}s asked the following question: given a graph $G$ and a directed graph $\vec{H}$, how many ways are there to orient the edges of $G$ such that it does not contain $\vec{H}$ as a subgraph? We denote this value by $D(G, \vec{H})$. Further, we let $D(n, \vec{H})$ denote the maximum of $D(G, \vec{H})$ over all graphs $G$ on $n$ vertices. In 2006, Alon and Yuster gave an exact answer when $\vec{H}$ is a tournament. In 2023, Buci\'c, Janzer, and Sudakov gave asymptotic answers for all directed graphs $\vec{H}$, and in the same paper, they gave an exact answer when $\vec{H}$ is a directed cycle. In this paper, we give a better bound for some specific non-bipartite directed graphs. Further, we obtain exact values of $D(G, \vec{H})$ for some small non-edge-critical directed graphs $\vec{H}$. Finally, for these graphs, we classify all graphs $G$ that attain the bound $D(G, \vec{H}) = D(n, \vec{H})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.