EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Orientations of Graphs With at Most One Directed Path Between Every Pair of Vertices

Barbora Dohnalová, Jiří Kalvoda, Gaurav Kucheriya, Sophie Spirkl

Journal of Graph Theory · 2026-09 · 113 (1) · 143-164

DOI: 10.1002/jgt.70060 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 05.05.2026. Verfasst von Barbora Dohnalová und 3 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada, Grantová Agentura České Republiky.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a graph , we say that an orientation of is a KT orientation if, for all , there is at most one directed path (in any direction) between and . Graphs that admit such orientations have been used to construct graphs with large chromatic number and small clique number that served as counterexamples to various conjectures. Motivated by this, we consider which graphs admit KT orientations (named after Kierstead and Trotter). In particular, we construct a graph family with small independence number (sub‐linear in the number of vertices) which admits a KT orientation. We show that the problem of determining whether a given graph admits a KT orientation is NP‐complete, even if we restrict ourselves to planar graphs. Finally, we provide an algorithm to decide if a graph with maximum degree at most 3 admits a KT orientation, whereas, for graphs with maximum degree 4, the problem remains NP‐complete.

Förderung

  • Natural Sciences and Engineering Research Council of Canada
  • Grantová Agentura České Republiky

Zitieren

APA

Dohnalová, B., Kalvoda, J., Kucheriya, G., & Spirkl, S. (2026). Orientations of Graphs With at Most One Directed Path Between Every Pair of Vertices. Journal of Graph Theory, 113(1), 143-164. https://doi.org/10.1002/jgt.70060

Vancouver

Dohnalová B, Kalvoda J, Kucheriya G, Spirkl S. Orientations of Graphs With at Most One Directed Path Between Every Pair of Vertices. Journal of Graph Theory. 2026;113(1):143-164. doi:10.1002/jgt.70060

BibTeX
@article{Dohnalov2026,
  author = {Dohnalová, Barbora and Kalvoda, Jiří and Kucheriya, Gaurav and Spirkl, Sophie},
  title = {Orientations of Graphs With at Most One Directed Path Between Every Pair of Vertices},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {113},
  number = {1},
  pages = {143--164},
  doi = {10.1002/jgt.70060}
}
Kostenlos starten →