Packing chromatic number versus chromatic and clique number

DOI10.1007/s00010-017-0520-9zbMath1390.05186arXiv1707.04910OpenAlexW2963791813MaRDI QIDQ1647755

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

Publication date: 26 June 2018

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

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

zbMATH Keywords

independence numberchromatic numberclique numberpacking chromatic numberMycielskian

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

Independence number and packing coloring of generalized Mycielski graphs ⋮ Packing chromatic numbers of finite super subdivisions of graphs ⋮ 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 ⋮ Graph classes generated by Mycielskians ⋮ Packing chromatic number of subdivisions of cubic graphs ⋮ Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs ⋮ Graphs that are critical for the packing chromatic number

Cites Work

• Unnamed Item
• Unnamed Item
• \(S\)-packing colorings of cubic graphs
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• The packing chromatic number of the infinite square lattice is between 13 and 15
• Complexity of the packing coloring problem for trees
• On the packing chromatic number of some lattices
• The packing chromatic number of infinite product graphs
• Packing chromatic number of cubic graphs
• Super connectivity and super edge connectivity of the Mycielskian of a graph
• 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
• Connectivity of the Mycielskian of a graph
• 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
• Several parameters of generalized Mycielskians
• Packing chromatic number of base-3 Sierpiński graphs
• 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
• Multi-coloring the Mycielskian of graphs
• The circular chromatic number of the Mycielskian ofGdk
• Packing Coloring of Undirected and Oriented Generalized Theta Graphs
• Mycielskians and matchings
• Sur le coloriage des graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

This page was built for publication: Packing chromatic number versus chromatic and clique number