Packing colouring of some classes of cubic graphs

MaRDI QIDQ4622625zbMATH OpenFDO

Authors Daouya Laïche, Éric Sopena

Publication date 13 February 2019

Full work available at URL https://arxiv.org/abs/1808.02675, http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p376.pdf

zbMATH Keywords

cubic graphsindependent setspacking coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The packing chromatic number $chi$ $ho$ (G) of a graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1 ,. .. , V k , in such a way that every two distinct vertices in V i are at distance greater than i in G for every i, 1 $le$ i $le$ k. Recently, Balogh, Kostochka and Liu proved that $chi$ $ho$ is not bounded in the class of subcubic graphs [Packing chromatic number of subcubic graphs, Discrete Math. 341 (2018), 474483], thus answering a question previously addressed in several papers. However, several subclasses of cubic or subcubic graphs have bounded packing chromatic number. In this paper, we determine the exact value of, or upper and lower bounds on, the packing chromatic number of some classes of cubic graphs, namely circular ladders, and so-called H-graphs and generalised H-graphs.

Recommendations

• Packing chromatic number of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• On the packing chromatic number of subcubic outerplanar graphs
• Packing colorings of subcubic outerplanar graphs
• \(S\)-packing colorings of cubic graphs

Cites work

• \(S\)-packing colorings of cubic graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Broadcast chromatic numbers of graphs
• scientific article; zbMATH DE number 2104737 (Why is no real title available?)
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• On the packing chromatic number of square and hexagonal lattice
• On the packing chromatic number of subcubic outerplanar graphs
• On the packing coloring of undirected and oriented generalized theta graphs
• Packing chromatic number of base-3 Sierpiński graphs
• Packing chromatic number of cubic graphs
• Packing chromatic number under local changes in a graph
• Packing chromatic number, (1, 1, 2, 2)-colorings, and characterizing the Petersen graph
• Packing coloring of Sierpiński-type graphs
• Packing coloring of some undirected and oriented coronae graphs
• Some large graphs with given degree and diameter
• The packing chromatic number of infinite product graphs

Cited in

(17)

• An infinite family of subcubic graphs with unbounded packing chromatic number
• Packing chromatic number versus chromatic and clique number
• Packing chromatic number of cubic graphs
• On the packing chromatic number of subcubic outerplanar graphs
• On S-packing edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Graphs that are critical for the packing chromatic number
• A survey on packing colorings
• The packing chromatic number of hypercubes
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• Polynomial instances of the packing coloring problem
• \(S\)-packing colorings of cubic graphs
• On packing coloring of helm related graphs
• AVD proper edge-coloring of some families of graphs
• Packing chromatic numbers of finite super subdivisions of graphs
• Packing chromatic number, (1, 1, 2, 2)-colorings, and characterizing the Petersen graph
• Bounds for packing chromatic number of some subclasses of trees

This page was built for publication: Packing colouring of some classes of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4622625)