Proper conflict-free 6-coloring of planar graphs without short cycles

Yunlong Wang, Weifan Wang and Runrun Liu

Applied Mathematics and Computation, 2025, vol. 499, issue C

Abstract: A proper conflict-free l-coloring of a graph G is a proper l-coloring satisfying that for any non-isolated vertex v∈V(G), there exists a color appearing exactly once in NG(v). The proper conflict-free chromatic number, denoted by χpcf(G), is the minimal integer l so that G admits a proper conflict-free l-coloring. This notion was proposed by Fabrici et al. in 2022. They focus mainly on proper conflict-free coloring of outerplanar graphs and planar graphs. They constructed a planar graph that has no proper conflict-free 5-coloring and conjectured every planar graph G has χpcf(G)≤6. In this paper, we confirm this conjecture for planar graphs without cycles of lengths 3, 5 or 6.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325001328
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:499:y:2025:i:c:s0096300325001328

DOI: 10.1016/j.amc.2025.129405

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 ().