Lune

SODA2026Top-tier venue

Centered colorings in minor-closed graph classes

Jedrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud

2026Year

Abstract

A vertex coloring \unicodex3C6\unicode{x3C6} of a graph GG is p-centered if for every connected subgraph HH of GG, either \unicodex3C6\unicode{x3C6} uses more than pp colors on HH, or there is a color that appears exactly once on HH. We prove that for every fixed positive integer tt, every KtK_t-minor-free graph admits a pp-centered coloring using O(pt−1)\mathcal O(p^{t-1}) 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.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

lune papers fulltext ba64c8f9-62ce-4d38-8d7b-598113f747ed

Builds on2

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines