Linear colorings of graphs

2025/05/05 by Hilaire, Claire, Krnc, Matjaž, Milanič, Martin +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.02768

Abstract

Motivated by algorithmic applications, Kun, O'Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two parameters are polynomially related. They conjectured that treedepth could be bounded from above by twice the linear chromatic number. In this paper we investigate the properties of linear chromatic number and provide improved bounds in several graph classes.

Citations

• Linear versus centred chromatic numbers
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• Improved bounds for the excluded-minor approximation of treedepth
• Polynomial Treedepth Bounds in Linear Colorings
• Separators in region intersection graphs
• Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs
• Testing first-order properties for subclasses of sparse graphs
• Grad and Classes with Bounded Expansion II. Algorithmic Aspects

Related

• Linear Coloring and Linear Graphs
• Polynomial Treedepth Bounds in Linear Colorings
• Linear versus centred chromatic numbers
• Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
• Separating Tree-chromatic number from Path-chromatic Number