On the Packing Coloring Gap of Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917510906904576 |
|---|---|
| author | Tarhini, Batoul Gözüpek, Didem |
| author_facet | Tarhini, Batoul Gözüpek, Didem |
| contents | The packing chromatic number of a graph is the minimum number of colors for which the graph admits a packing coloring. This distance-based parameter may change under local structural modifications of the graph. In this paper, we introduce the packing coloring gap, defined as the maximum decrease in the packing chromatic number caused by the deletion of a single vertex. We focus on trees and determine the packing coloring gap for caterpillars. We further extend these results to caterpillars under the corona operation with K1. In addition, we present examples of graphs with packing coloring gap zero, one, and arbitrarily large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_16680 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Packing Coloring Gap of Graphs Tarhini, Batoul Gözüpek, Didem Combinatorics The packing chromatic number of a graph is the minimum number of colors for which the graph admits a packing coloring. This distance-based parameter may change under local structural modifications of the graph. In this paper, we introduce the packing coloring gap, defined as the maximum decrease in the packing chromatic number caused by the deletion of a single vertex. We focus on trees and determine the packing coloring gap for caterpillars. We further extend these results to caterpillars under the corona operation with K1. In addition, we present examples of graphs with packing coloring gap zero, one, and arbitrarily large. |
| title | On the Packing Coloring Gap of Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.16680 |