EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs

Reza Naserasr, Lan Anh Pham, Cyril Pujol, Huan Zhou

Journal of Graph Theory · 2026-09 · 113 (1) · 5-18

DOI: 10.1002/jgt.70047 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 18.04.2026. Verfasst von Reza Naserasr und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Agence Nationale de la Recherche.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A balanced ‐coloring of a signed graph is an assignment of colors to each vertex of from a platter of colors, such that each color class induces a balanced set (a set that does not induce a negative cycle). The fractional balanced chromatic number of , denoted , is the minimum ratio such that has a balanced ‐coloring. This value is bounded by the fractional arboricity of , denoted , which is defined so that each color class induces an acyclic subgraph of . In this work we present an example of a signed planar simple graph of fractional balanced chromatic number greater than 2, in particular, refuting a conjecture of Bonamy, Kardoš, Kelly, and Postle suggesting that the fractional arboricity of planar graphs is bounded above by 2. By iterating the construction, we show that the supremum of the fractional balanced chromatic number of signed planar simple graphs is at least . Our method results in a construction of a planar graph on 34 vertices whose fractional arboricity is .

Förderung

  • Agence Nationale de la Recherche

Zitieren

APA

Naserasr, R., Pham, L. A., Pujol, C., & Zhou, H. (2026). Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs. Journal of Graph Theory, 113(1), 5-18. https://doi.org/10.1002/jgt.70047

Vancouver

Naserasr R, Pham LA, Pujol C, Zhou H. Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs. Journal of Graph Theory. 2026;113(1):5-18. doi:10.1002/jgt.70047

BibTeX
@article{Naserasr2026,
  author = {Naserasr, Reza and Pham, Lan Anh and Pujol, Cyril and Zhou, Huan},
  title = {Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {113},
  number = {1},
  pages = {5--18},
  doi = {10.1002/jgt.70047}
}
Kostenlos starten →