Packing chromatic number of cubic graphs

DOI10.1016/J.DISC.2017.09.014MaRDI QIDQ1686001zbMATH OpenOpenAlexFDO

Authors József Balogh, Xujun Liu, Alexandr Kostochka

Publication date 20 December 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.09873

zbMATH Keywords

cubic graphsindependent setspacking coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,ldots,V_k$ such that for each $1leqileqk$ the distance between any two distinct $x,yin{V}_i$ is at least $i+1$. The packing chromatic number, $ch{i}_p(G)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $ggeq2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.

Recommendations

• Packing colouring of some classes of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Packing colorings of subcubic outerplanar graphs
• \(S\)-packing colorings of cubic graphs
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs

Cites work

• \(S\)-packing colorings of cubic graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Broadcast chromatic numbers of graphs
• Complexity of the packing coloring problem for trees
• Dichotomies properties on computational complexity of S-packing coloring problems
• Facial packing edge-coloring of plane graphs
• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• scientific article; zbMATH DE number 3600068 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• 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 under local changes in a graph
• Packing chromatic number, (1, 1, 2, 2)-colorings, and characterizing the Petersen graph
• Packing coloring of some undirected and oriented coronae graphs
• The asymptotic number of labeled graphs with given degree sequences
• The Independence Ratio of Regular Graphs
• The packing chromatic number of infinite product graphs
• The packing coloring problem for lobsters and partner limited graphs

Cited in

(43)

• Packing coloring of Sierpiński-type graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Notes on complexity of packing coloring
• Packing chromatic number versus chromatic and clique number
• On the packing chromatic number of subcubic outerplanar graphs
• Facial packing vertex-coloring of subdivided plane graphs
• On S-packing edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• On S-packing edge-colorings of graphs with small edge weight
• Graphs that are critical for the packing chromatic number
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• A survey on packing colorings
• \(S\)-packing chromatic vertex-critical graphs
• Packing colorings of subcubic outerplanar graphs
• On the packing chromatic number of Moore graphs
• Independence number and packing coloring of generalized Mycielski graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• \(S\)-packing colorings of cubic graphs
• Packing chromatic number of distance graphs
• Packing colouring of some classes of cubic graphs
• Packing chromatic numbers of finite super subdivisions of graphs
• Packing chromatic number under local changes in a graph
• Packing in regular graphs
• Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
• The exponential growth of the packing chromatic number of iterated Mycielskians
• On packing \(S\)-colorings of subcubic graphs
• About S-packing coloring of subcubic graphs
• On uniquely packable trees
• Packing chromatic number of windmill related graphs and chain silicate networks
• Packing coloring of hypercubes with extended Hamming codes
• On S-packing coloring of 2-saturated subcubic graphs
• Partial packing coloring and quasi-packing coloring of the triangular grid
• Bounds for packing chromatic number of some subclasses of trees
• On S-packing edge-colorings of subcubic claw-free graphs
• On S-packing colorings of subcubic graphs
• Every subcubic graph is packing (1,1,2,2,3)-colorable
• Grundy packing coloring of graphs
• Further results and questions on S-packing coloring of subcubic graphs
• On the (1, 1, 2, 3)-packing coloring of some subcubic graphs
• A short proof that every claw-free cubic graph is (1, 1, 2, 2)-packing colorable
• Packing edge-colorings of subcubic outerplanar graphs
• On the packing chromatic number of some lattices

This page was built for publication: Packing chromatic number of cubic graphs

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