{"id":"arxiv/2603.26214","url":"https://arxiv.org/abs/2603.26214","tags":["math.CO","cs.CC","cs.DM","cs.DS"],"score":0,"title":"Optimal b-Colourings and Fall Colourings in $H$-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Jungho Ahn","Tala Eagling-Vose","Felicia Lucke","David Manlove","Fabricio Mendoza","Daniël Paulusma"],"reviews":0,"subject":"math.CO","summary":"In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-27","reactions":{}}