Metraipolis › archive › dc_23e514b94dd3

Bounded-Defect Proper Orientations and Graphs on Surfaces — arXiv:2609.30315

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.30315
License (as archived): CC0-1.0
Archived: 2026-10-08T02:59:08.438Z
SHA-256 of the archived text: 8444c49b2127dd3f1eb2809f18be7159d25072b269c6d487fc333eae69f49219
Stable URL of this page: https://metraipolis.com/documento/dc_23e514b94dd3

How to cite

Bounded-Defect Proper Orientations and Graphs on Surfaces — arXiv:2609.30315 — arXiv (en), https://arxiv.org/abs/2609.30315 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_23e514b94dd3 (Metraipolis archive dc_23e514b94dd3, sha256 8444c49b2127dd3f1eb2809f18be7159d25072b269c6d487fc333eae69f49219)

BibTeX

@misc{dc23e514b94dd3,
  title = {Bounded-Defect Proper Orientations and Graphs on Surfaces — arXiv:2609.30315},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30315},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_23e514b94dd3; sha256 8444c49b2127dd3f1eb2809f18be7159d25072b269c6d487fc333eae69f49219},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30315. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Chen, Mohar and Wu [J. Combin. Theory Ser. B 161 (2023)] conjectured that every graph of orientable genus $g$ has proper orientation number $O(\sqrt g)$. We prove this conjecture. Our main result extends the potential-outdegree method from independent color classes to three parts of bounded internal degree. Let $k,D\in\mathbb Z_{\ge0}$. If $G$ has maximum average degree at most $2k$ and $V(G)=V_1\cup V_2\cup V_3$, where each $V_i$ induces a subgraph of maximum degree at most $D$, then $$\pchi(G)\le k+9D+6+\floor{\frac32\ceil{\frac{2D+2}{5}}}\le k+\floor{\frac{48D}{5}}+8.$$ When the partition is given, we construct such an orientation in polynomial time. For every $D\ge1$, we also construct a graph with a partition into three parts of internal maximum degree at most $D$ for which $\pchi(G)-\ceil{\mad(G)/2}\ge6D+5$; hence the linear dependence on $D$ is unavoidable. Finally, Woodall's defective-coloring theorem yields $\pchi(G)=O(\sqrt{\gamma+1})$ for every graph of Euler genus $\gamma$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.30315 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:28:17.902Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).