Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 3 min ago
PreprintarXiv licencearXiv

Oriented paths with two blocks in bipartite oriented graphs

  • Bin Chen
  • Meishuang Chen
  • Xinmin Hou
  • Xinyu Zhou
Open at sourcePDFDOICite

Abstract

Stein conjectured that for any integer k≥ 2, every oriented graph with minimum semidegree greater than k/2 contains every orientation of a path with k edges. Recently, Chen, Hou and Zhou proved this conjecture to be true for any oriented path with two blocks, where a block of an oriented path is a maximal directed subpath within it. In this paper, we prove that every bipartite oriented graph with minimum semidegree at least 3k/8+2 contains every oriented path with two blocks of length k for k≥ 2. Moreover, in contrast to the general oriented setting, we highlight that the minimum semidegree threshold in the bipartite setting is closely related to the number of blocks.

Related

  1. Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
    Yihang Liu, Zhenyu Yang, Yuwan Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Two-block paths in oriented graphs under the Ore-type condition
    Ke Zhao, Jia Zhou, Yunshu Gao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Oriented Paths with Few Direction Flips Are Tournament Anti-Sidorenko
    Hao Chen, Yupeng Lin
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. When are random regular triangle-free graphs bipartite?
    Gregory DeCamillis, Pu Gao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Negative edge correlation in complete bipartite graphs
    Ying Cao, Houshan Fu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026oriented,
  title = {{Oriented paths with two blocks in bipartite oriented graphs}},
  author = {Bin Chen and Meishuang Chen and Xinmin Hou and Xinyu Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.09935},
  eprint = {2609.09935},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.09935},
}
RIS
TY  - UNPB
TI  - Oriented paths with two blocks in bipartite oriented graphs
AU  - Bin Chen
AU  - Meishuang Chen
AU  - Xinmin Hou
AU  - Xinyu Zhou
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.09935
UR  - https://arxiv.org/abs/2609.09935
AB  - Stein conjectured that for any integer k≥ 2, every oriented graph with minimum semidegree greater than k/2 contains every orientation of a path with k edges. Recently, Chen, Hou and Zhou proved this conjecture to be true for any oriented path with two blocks, where a block of an oriented path is a maximal directed subpath within it. In this paper, we prove that every bipartite oriented graph with minimum semidegree at least 3k/8+2 contains every oriented path with two blocks of length k for k≥ 2. Moreover, in contrast to the general oriented setting, we highlight that the minimum semidegree threshold in the bipartite setting is closely related to the number of blocks.
ER  -