Packing (1,1,2,2)-coloring of some subcubic graphs
| Autor: | Gexin Yu, Martin Rolek, Xujun Liu, Runrun Liu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Conjecture
Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Petersen graph Discrete Mathematics and Combinatorics Partition (number theory) Mathematics |
| Zdroj: | Discrete Applied Mathematics. 283:626-630 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.03.015 |
| Popis: | For a sequence of non-decreasing positive integers S = ( s 1 , … , s k ) , a packing S -coloring is a partition of V ( G ) into sets V 1 , … , V k such that for each 1 ≤ i ≤ k the distance between any two distinct x , y ∈ V i is at least s i + 1 . The smallest k such that G has a packing ( 1 , 2 , … , k ) -coloring is called the packing chromatic number of G and is denoted by χ p ( G ) . For a graph G , let D ( G ) denote the graph obtained from G by subdividing every edge. The question whether χ p ( D ( G ) ) ≤ 5 for all subcubic graphs G was first asked by Gastineau and Togni and later conjectured by Bresar, Klavžar, Rall and Wash. Gastineau and Togni observed that if one can prove every subcubic graph except the Petersen graph is packing ( 1 , 1 , 2 , 2 ) -colorable then the conjecture holds. The maximum average degree, mad( G ), is defined to be max { 2 | E ( H ) | | V ( H ) | : H ⊂ G } . In this paper, we prove that subcubic graphs with m a d ( G ) 30 11 are packing ( 1 , 1 , 2 , 2 ) -colorable. As a corollary, the conjecture of Bresar et al holds for every subcubic graph G with m a d ( G ) 30 11 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect