On S-Packing Coloring of Subcubic Graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917354329341952 |
|---|---|
| author | Bazzal, Hadeel Al |
| author_facet | Bazzal, Hadeel Al |
| contents | Given a sequence \( S = (s_1, s_2, \ldots, s_k) \) of positive integers satisfying \( s_1 \leq s_2 \leq \dots \leq s_k \), an \( S \)-packing coloring of a graph \( G \) is a partition of \( V(G) \) into \( k \) subsets \( V_1, V_2, \dots, V_k \) such that, for each \( 1 \leq i \leq k \), the distance between any two distinct vertices \( x, y \in V_i \) is at least \( s_i + 1 \). Yang and Wu established that every $3$-irregular subcubic graph admits a \( (1,1,3) \)-packing coloring. Later, Mortada and Togni introduced the concept of an \( i \)-saturated subcubic graph, defined as a subcubic graph in which every vertex of degree three has at most \( i \) neighbors of degree three for \( 0 \leq i \leq 3 \). They further demonstrated that all $1$-saturated subcubic graphs are \( (1,1,2) \)-packing colorable. In this paper, we present new concise proofs of these results using a novel tool. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01769 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On S-Packing Coloring of Subcubic Graphs Bazzal, Hadeel Al Combinatorics Given a sequence \( S = (s_1, s_2, \ldots, s_k) \) of positive integers satisfying \( s_1 \leq s_2 \leq \dots \leq s_k \), an \( S \)-packing coloring of a graph \( G \) is a partition of \( V(G) \) into \( k \) subsets \( V_1, V_2, \dots, V_k \) such that, for each \( 1 \leq i \leq k \), the distance between any two distinct vertices \( x, y \in V_i \) is at least \( s_i + 1 \). Yang and Wu established that every $3$-irregular subcubic graph admits a \( (1,1,3) \)-packing coloring. Later, Mortada and Togni introduced the concept of an \( i \)-saturated subcubic graph, defined as a subcubic graph in which every vertex of degree three has at most \( i \) neighbors of degree three for \( 0 \leq i \leq 3 \). They further demonstrated that all $1$-saturated subcubic graphs are \( (1,1,2) \)-packing colorable. In this paper, we present new concise proofs of these results using a novel tool. |
| title | On S-Packing Coloring of Subcubic Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.01769 |