DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.2

Optimal b-Colourings and Fall Colourings in H-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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 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.

Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniël Paulusma. Optimal b-Colourings and Fall Colourings in H-Free Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.WG.2026.2,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Manlove, David and Mendoza Granada, Fabricio and Paulusma, Dani\"{e}l},
  title =	{{Optimal b-Colourings and Fall Colourings in H-Free Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.2},
  URN =		{urn:nbn:de:0030-drops-261685},
  doi =		{10.4230/LIPIcs.WG.2026.2},
  annote =	{Keywords: b-chromatic number, tight graph, fall achromatic number, fall chromatic number, H-free graph}
}

Search Results

Documents authored by Mendoza Granada, Fabricio

Optimal b-Colourings and Fall Colourings in H-Free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message