An identifying operation on a 1-planar graph with an application to acyclic coloring

Qiuyue Tan, Haizhen Qiu, Yiqiao Wang and Kan Wang

Applied Mathematics and Computation, 2026, vol. 508, issue C

Abstract: This paper introduces a graph operation and gives its applications. Given a 1-plane graph M and its crossing point x formed by two crossing edges uu′ and vv′, an Identifying Operation with respect to x is defined in two steps: (1) identifying u and v such that x vanishes; (2) deleting loops and multi-edges (if exists). Using Identifying Operation to every crossing point, we change M into its associated plane graph M⁎. Under some conditions, we show that χa(M)≤2χa(M⁎), where the parameters χa(M) and χa(M⁎) represent the acyclic-chromatic-number of M and M⁎, respectively. This generalizes a result established by Yang et al. in 2018.

Keywords: Identifying operation; Acyclic coloring; 1-planar graph; IC-planar graph (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325003406
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:508:y:2026:i:c:s0096300325003406

DOI: 10.1016/j.amc.2025.129614

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().