Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph

DOI10.1007/s00010-016-0461-8zbMath1355.05194arXiv1608.05573OpenAlexW2509630417MaRDI QIDQ509625

Sandi Klavžar, Boštjan Brešar, Kirsti Wash, Douglas F. Rall

Publication date: 17 February 2017

Published in: Aequationes Mathematicae (Search for Journal in Brave)

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

zbMATH Keywords

subdivisioncubic graphPetersen graphgeneralized prismpacking chromatic numberS-coloring

Mathematics Subject Classification ID

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

Related Items (22)

Packing coloring of Sierpiński-type graphs ⋮ An infinite family of subcubic graphs with unbounded packing chromatic number ⋮ 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 ⋮ Packing chromatic number of cubic graphs ⋮ Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs ⋮ A survey on packing colorings ⋮ \(S\)-packing coloring of cubic Halin graphs ⋮ 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 \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\) ⋮ On the packing chromatic number of subcubic outerplanar graphs ⋮ Facial packing vertex-coloring of subdivided plane graphs ⋮ Packing chromatic number of subdivisions of cubic graphs ⋮ The packing chromatic number of the infinite square lattice is between 13 and 15 ⋮ A GENERAL POSITION PROBLEM IN GRAPH THEORY ⋮ \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\) ⋮ Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs ⋮ Packing colouring of some classes of cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(S\)-packing colorings of cubic graphs
• Packing chromatic number under local changes in a graph
• A characterization of cubic graphs with paired-domination number three-fifths their order
• Complexity of the packing coloring problem for trees
• On the packing chromatic number of some lattices
• The packing chromatic number of infinite product graphs
• A lower bound for the packing chromatic number of the Cartesian product of cycles
• Modeling the packing coloring problem of graphs
• The packing chromatic number of hypercubes
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• The packing coloring of distance graphs \(D(k,t)\)
• On packing colorings of distance graphs
• The packing coloring problem for lobsters and partner limited graphs
• Packing chromatic number of base-3 Sierpiński graphs
• A note on \(S\)-packing colorings of lattices
• The S-packing chromatic number of a graph
• On the packing chromatic number of square and hexagonal lattice
• Subdivision into i-packings and S-packing chromatic number of some lattices
• Some large graphs with given degree and diameter
• Packing Coloring of Undirected and Oriented Generalized Theta Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

This page was built for publication: Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph