Partitioning of a graph into induced subgraphs not containing prescribed cliques

DOI10.1016/j.dam.2023.11.001zbMath1529.05134arXiv2210.04967OpenAlexW4388679251MaRDI QIDQ6180565

Yaser Rowshan, Ali Taherkhani

Publication date: 22 December 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringgraph partitioningBorodin-Kostochka conjecture\(G\)-free coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graphs with chromatic number close to maximum degree
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• \(\Delta \)-critical graphs with small high vertex cliques
• Brooks' graph-coloring theorem and the independence number
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Another bound on the chromatic number of a graph
• A strengthening of Brooks' theorem
• The complexity of \(G\)-free colourability
• Vertex arboricity and maximum degree
• Partitioning and coloring graphs with degree constraints
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• The point-arboricity of a graph
• Graphs with $\chi=\Delta$ Have Big Cliques
• On hitting all maximum cliques with an independent set
• Optimal Vertex Partitions
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• A Note on Hitting Maximum and Maximal Cliques With a Stable Set
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item