Centered colorings in minor-closed graph classes
Jedrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud
2026Year
Abstract
A vertex coloring of a graph is p-centered if for every connected subgraph of , either uses more than colors on , or there is a color that appears exactly once on . We prove that for every fixed positive integer , every -minor-free graph admits a -centered coloring using colors.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext ba64c8f9-62ce-4d38-8d7b-598113f747edBuilds on2
Related papers
- Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
- Faster (Δ+1)-Edge Coloring: Breaking the m√n Time BarrierSayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon et al.FOCS 2024 · 5 citations
- Vizing's Theorem in Deterministic Almost-Linear TimeSepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa et al.SODA 2026
- The Erdős-Pósa property for circle graphs as vertex-minorsRutger Campbell, Jochen Pascal Gollin, Meike Hatzel, O-joung Kwon et al.SODA 2026 · 5 citations
- Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of RecognitionTuukka Korhonen, Daniel LokshtanovSODA 2024 · 7 citations
