Sparse Partitions of Graphs with Bounded Clique Number

2024/11/29 by António Girão, Girão, António, Toby Insley +1
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2411.19915

Abstract

We prove that for each integer r≥ 2, there exists a constant C_r>0 with the following property: for any 0<ε ≤ 1/2 and any graph G with clique number at most r, there is a partition of V(G) into at most (1/ε)^C_r sets S₁, …, S_t, such that G[S_i] has maximum degree at most ε |S_i| for each 1 ≤ i ≤ t. This answers a question of Fox, Nguyen, Scott and Seymour, who proved a similar result for graphs with no induced P₄.

Related

• Partitioning graphs with linear minimum degree
• Partitioning sparse graphs into an independent set and a forest of\n bounded degree
• Partitioning a graph into a cycle and a sparse graph
• On cuts of small chromatic number in sparse graphs
• On graphs with a simple structure of maximal cliques