{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib6y6ojck24tmecajd7tzcoo55anvvypcpdqtwolhry3yqfbzru6u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mibqeskinbp2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.26214v1",
  "publishedAt": "2026-03-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jungho Ahn",
    "Tala Eagling-Vose",
    "Felicia Lucke",
    "David Manlove",
    "Fabricio Mendoza",
    "Daniël Paulusma"
  ],
  "textContent": "**Authors:** Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza, Daniël Paulusma\n\nIn 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 $H$-free graphs. For Tight b-Chromatic Number in $H$-free graphs, we develop a general technique to determine new graphs $H$, for which the problem is polynomial-time solvable, and we also determine new graphs $H$, for which the problem is still NP-complete. We show, for the first time, the existence of a graph $H$ such that in $H$-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.",
  "title": "Optimal b-Colourings and Fall Colourings in $H$-Free Graphs"
}