Fractional Balanced Chromatic Number and Arboricity of Planar (Signed) Graphs
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.
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}
}
EUVIMED