Packing chromatic number of cubic graphs

DOI10.1016/j.disc.2017.09.014zbMath1376.05047arXiv1703.09873OpenAlexW2604505313MaRDI QIDQ1686001

József Balogh, Xujun Liu, Alexandr V. 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

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

Related Items (24)

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 ⋮ Independence number and packing coloring of generalized Mycielski graphs ⋮ Packing chromatic numbers of finite super subdivisions of graphs ⋮ On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs ⋮ Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable ⋮ The exponential growth of the packing chromatic number of iterated Mycielskians ⋮ Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs ⋮ A survey on packing colorings ⋮ On packing \(S\)-colorings of subcubic graphs ⋮ \(S\)-packing chromatic vertex-critical graphs ⋮ Packing colorings of subcubic outerplanar graphs ⋮ About \(S\)-packing coloring of subcubic graphs ⋮ On the packing chromatic number of Moore graphs ⋮ 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 ⋮ Packing colouring of some classes of cubic graphs ⋮ On \(S\)-packing edge-colorings of graphs with small edge weight ⋮ Graphs that are critical for the packing chromatic number

Cites Work

• \(S\)-packing colorings of cubic graphs
• Facial packing edge-coloring of plane graphs
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• Complexity of the packing coloring problem for trees
• The packing chromatic number of infinite product graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• On the packing chromatic number of subcubic outerplanar graphs
• Packing coloring of some undirected and oriented coronae graphs
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• The packing coloring problem for lobsters and partner limited graphs
• Packing chromatic number of base-3 Sierpiński graphs
• On the packing chromatic number of square and hexagonal lattice
• The Independence Ratio of Regular Graphs
• Packing Coloring of Undirected and Oriented Generalized Theta Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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