pith. sign in

arxiv: 2603.26214 · v2 · submitted 2026-03-27 · 🧮 math.CO · cs.CC· cs.DM· cs.DS

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

Jungho Ahn , Tala Eagling-Vose , Felicia Lucke , David Manlove , Fabricio Mendoza , Dani\"el Paulusma This is my paper

Pith reviewed 2026-05-14 23:12 UTC · model grok-4.3

classification 🧮 math.CO cs.CCcs.DMcs.DS MSC 05C1568Q25
keywords b-chromatic numberfall chromatic numberH-free graphscomputational complexityNP-hardnesspolynomial-time algorithmscolouring problems
0
0 comments X

The pith

For some forbidden subgraphs H, computing the b-chromatic number of H-free graphs is NP-hard while the tight b-chromatic number is solvable in polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies the computational complexity of four colouring problems in H-free graphs by combining existing results with new reductions. It proves that b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number each admit a complete dichotomy: for every fixed H the problem is either polynomial-time solvable or NP-complete. For Tight b-Chromatic Number the authors supply a general technique that produces new families of H for which the problem is in P and other families for which it remains NP-complete. The key separation result is the first explicit H for which the unrestricted b-chromatic number is hard yet the tight variant is tractable.

Core claim

By combining known and new results, the authors 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 they develop a general technique that identifies new graphs H making the problem polynomial-time solvable and others for which it stays NP-complete; they exhibit, for the first time, an explicit graph H such that b-Chromatic Number is NP-hard on H-free graphs while Tight b-Chromatic Number is polynomial-time solvable.

What carries the argument

The b-chromatic vertex (a vertex adjacent to all other colours) together with the three-way framework that requires every colour class to contain at least one, exactly one, or all b-chromatic vertices.

If this is right

  • The complexity of each of the four problems is now known for every fixed forbidden subgraph H.
  • There exist H-free graph classes where the b-chromatic number is hard yet a natural restriction remains tractable.
  • The same separation technique can be applied to other colouring parameters that refine the standard chromatic number.
  • Algorithm designers now have a concrete list of H-free classes on which each problem can be solved efficiently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation between b-chromatic and tight b-chromatic number may indicate that the extra constraint of exactly one b-vertex per class removes the source of hardness for certain H.
  • Similar separations could exist for other graph parameters whose definitions involve counting or selecting distinguished vertices inside colour classes.
  • The general technique for identifying new polynomial cases for Tight b-Chromatic Number may extend to related problems such as equitable colouring or defective colouring.

Load-bearing premise

The new reductions together with prior results are assumed to partition every possible forbidden graph H into the correct complexity class without leaving any H unclassified.

What would settle it

An explicit forbidden graph H for which the b-chromatic number on H-free graphs can be computed in polynomial time while the tight b-chromatic number is NP-complete, or vice versa.

Figures

Figures reproduced from arXiv: 2603.26214 by Dani\"el Paulusma, David Manlove, Fabricio Mendoza, Felicia Lucke, Jungho Ahn, Tala Eagling-Vose.

Figure 9
Figure 9. Figure 9: Note that G′ is C3-free and F(G′ ) = {3}. It remains to observe that G + G′ is C3-free, and also that G has a fall 3-colouring if and only if G + G′ is fall-unique. ◀ ▶ Lemma 30 ([36]). Fall Chromatic Number and Fall Achromatic Number are NP-hard for line graphs, and thus for claw-free graphs. Proof. We recall that Lauri and Mitillos [36] proved that Fall 3-Colouring is NP-complete even for 4-regular line … view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript classifies the computational complexity of b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number, and Fall Achromatic Number on H-free graphs. It combines prior results with new reductions to obtain a full dichotomy for three of the problems and develops a general technique for identifying new forbidden graphs H under which Tight b-Chromatic Number is polynomial-time solvable or remains NP-complete. A concrete graph H is exhibited for which b-Chromatic Number is NP-hard while Tight b-Chromatic Number is polynomial-time solvable.

Significance. If the claimed classifications and reductions hold, the work supplies the first complete complexity landscape for these b-coloring and fall-coloring variants on hereditary graph classes. The explicit separation between b-Chromatic Number and Tight b-Chromatic Number is novel and demonstrates that the two problems can diverge in complexity even within the same H-free class. The general technique for determining new polynomial cases for Tight b-Chromatic Number strengthens the methodological toolkit for similar dichotomy results.

major comments (1)
  1. The section presenting the concrete graph H and the accompanying reduction for NP-hardness of b-Chromatic Number must explicitly verify that the construction forbids exactly the intended subgraphs and that no additional polynomial-time cases are inadvertently created.
minor comments (2)
  1. The introduction should more clearly delineate which parts of the classification are taken from prior literature and which parts rely on the new reductions introduced here.
  2. Notation for the four problem variants is introduced in the abstract but would benefit from a consolidated table in Section 2 that lists the precise conditions on b-chromatic vertices for each variant.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation and recommendation of minor revision. We address the single major comment below and will make the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: The section presenting the concrete graph H and the accompanying reduction for NP-hardness of b-Chromatic Number must explicitly verify that the construction forbids exactly the intended subgraphs and that no additional polynomial-time cases are inadvertently created.

    Authors: We agree that an explicit verification strengthens the presentation. In the revised manuscript we will insert a short dedicated paragraph immediately after the definition of H and the description of the reduction. This paragraph will (i) list the minimal forbidden subgraphs induced by H and confirm that the construction contains no others, and (ii) argue that any additional forbidden subgraph would either violate the minimality of H or create a class already covered by the polynomial-time cases identified via the general technique earlier in the paper. The argument relies only on the structural properties already used to prove NP-hardness and does not alter the claimed dichotomy. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper classifies the complexity of b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number on H-free graphs by combining external known results with new reductions and an explicit concrete graph H that separates the first two problems. No equations, fitted parameters, self-definitional loops, or load-bearing self-citations appear in the derivation; the claimed dichotomy rests on independent combinatorial reductions whose correctness is verifiable outside the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions of b-chromatic vertices and on known NP-completeness results for coloring problems; no new free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of b-chromatic vertices and H-free graphs together with known complexity results for related coloring problems
    The classification combines these background facts with new reductions.

pith-pipeline@v0.9.0 · 5535 in / 1242 out tokens · 31654 ms · 2026-05-14T23:12:59.988777+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Optimal b-colourings and fall colourings inH-free graphs.Proc

    1 Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, David Manlove, Fabricio Mendoza Granada, and Daniel Paulusma. Optimal b-colourings and fall colourings inH-free graphs.Proc. WG 2026, Leibniz International Proceedings in Informatics, to appear, 326:12:1–12:16,

    work page 2026

  2. [2]

    2 Itai Benjamini.Coarse Geometry and Randomness, École d’Été de Probabilités de Saint- Flour XLI – 2011, volume 2100 ofLecture Notes in Mathematics

    doi:10.4230/LIPIcs.WG.2026.12. 2 Itai Benjamini.Coarse Geometry and Randomness, École d’Été de Probabilités de Saint- Flour XLI – 2011, volume 2100 ofLecture Notes in Mathematics. Springer,

    work page doi:10.4230/lipics.wg.2026.12 2026

  3. [3]

    3 Jan Bok, Nikola Jedlicková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith

    doi: 10.1007/978-3-319-02576-6. 3 Jan Bok, Nikola Jedlicková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith. Acyclic, star and injective colouring: A complexity picture forH-free graphs.Journal of Computer and System Sciences, 154:103662, 2025.doi:10.1016/j.jcss.2025.103662. 4 Édouard Bonnet, Florent Foucaud, Eun Jung Kim, and Florian Sik...

    work page doi:10.1007/978-3-319-02576-6 2025

  4. [4]

    7 Andreas Brandstädt, Van Bang Le, and Jeremy P

    doi:10.1007/s00453-014-9921-5. 7 Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad.Graph Classes: A Survey. SIAM, 1999.doi:10.1137/1.9780898719796. 8 Victor A. Campos, Carlos Vinícius G. C. Lima, Nicolas Almeida Martins, Leonardo Sampaio Rocha, Marcio Costa Santos, and Ana Silva. The b-chromatic index of graphs.Discrete Mathematics, 338:2072–2079, 20...

    work page doi:10.1007/s00453-014-9921-5 1999

  5. [5]

    11 Bruno Courcelle, Johann A

    doi:10.1007/S00453-016-0240-X. 11 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33:125–150,

    work page doi:10.1007/s00453-016-0240-x

  6. [6]

    Makowsky, and Udi Rotics

    doi:10.1007/s002249910009. 12 Konrad K. Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs.Compututer Journal, 59:650–666, 2016.doi:10.1093/comjnl/ bxv096. 13 Jean E Dunbar, Sandra M Hedetniemi, ST Hedetniemi, David P Jacobs, J Knisely, RC Laskar, and Douglas F Rall. Fall colorings of graphs.Journal of ...

    work page doi:10.1007/s002249910009 2016

  7. [7]

    A distributed algorithm for a b-coloring of a graph.Proc

    15 Brice Effantin and Hamamache Kheddouci. A distributed algorithm for a b-coloring of a graph.Proc. IPSA 2006, Lecture Notes in Computer Science, 4330:430–438,

    work page 2006

  8. [8]

    doi: 10.1007/11946441_42. J. Ahn, T. Eagling-Vose, F. Lucke, D. Manlove, F. Mendoza, D. Paulusma 25 16 Haytham Elghazel, Véronique Deslandres, Mohand-Said Hacid, Alain Dussauchoy, and Hama- mache Kheddouci. A new clustering approach for symbolic data and its validation: Application to the healthcare data.Proc. ISMIS 2006, Lecture Notes in Computer Science...

    work page doi:10.1007/11946441_42 2006

  9. [9]

    18 Djamel Gaceb, Véronique Eglin, Frank Lebourgeois, and Hubert Emptoz

    doi:10.48550/arXiv.2403.05943. 18 Djamel Gaceb, Véronique Eglin, Frank Lebourgeois, and Hubert Emptoz. Improvement of postal mail sorting system.International Journal of Document Analysis and Recognition (IJDAR), 11(2):67–80, 2008.doi:10.1007/s10032-008-0070-8. 19 Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computati...

    work page doi:10.48550/arxiv.2403.05943 2008

  10. [10]

    The NP-completeness of edge-coloring.SIAM Journal on Computing, 10:718–720, 1981.doi:10.1137/0210055

    23 Ian Holyer. The NP-completeness of edge-coloring.SIAM Journal on Computing, 10:718–720, 1981.doi:10.1137/0210055. 24 Robert W. Irving and David F. Manlove. The b-chromatic number of a graph.Discrete Applied Mathematics, 91:127–141, 1999.doi:10.1016/S0166-218X(98)00146-2. 25 Lars Jaffke and Paloma T. Lima. A complexity dichotomy for critical values of t...

    work page doi:10.1137/0210055 1981

  11. [11]

    29 Tommy R

    doi: 10.1016/j.jcss.2025.103754. 29 Tommy R. Jensen and Bjarne Toft.Graph Coloring Problems. Wiley, 1995.doi:10.1002/ 9781118032497. 30 Ivo Koch and Javier Marenco. An integer programming approach to b-coloring.Discrete Optimization, 32:43–62, 2019.doi:10.1016/j.disopt.2018.12.001. 31 Guy Kortsarz and Sunil Shende. An improved approximation of the achroma...

    work page doi:10.1016/j.jcss.2025.103754 2025

  12. [12]

    Laskar and Jeremy Lyle

    35 Renu C. Laskar and Jeremy Lyle. Fall colouring of bipartite graphs and cartesian products of graphs.Discrete Applied Mathematics, 157:330–338, 2009.doi:10.1016/j.dam.2008.03.003. 26 Optimal b-Colourings and Fall Colourings inH-Free Graphs 36 Juho Lauri and Christodoulos Mitillos. Complexity of fall coloring for restricted graph classes. Theory of Compu...

    work page doi:10.1016/j.dam.2008.03.003 2009

  13. [13]

    40 Jeremy Lyle, Nathan Drake, and Renu C

    LAGOS 2009 – V Latin-American Algorithms, Graphs and Optimization Symposium.doi:10.1016/j.endm.2009.11.035. 40 Jeremy Lyle, Nathan Drake, and Renu C. Laskar. Independent domatic partitioning or fall coloring of strongly chordal graphs.Congressus Numerantium, 172:149–159,

    work page doi:10.1016/j.endm.2009.11.035 2009

  14. [14]

    43 Cristopher Moore and John Michael Robson

    URL:https://repository.iit.edu/islandora/object/islandora%3A7430. 43 Cristopher Moore and John Michael Robson. Hard tiling problems with simple tiles.Discrete and Computational Geometry, 26:573–590, 2001.doi:10.1007/s00454-001-0047-6. 44 Stephan Olariu. Paw-free graphs.Information Processing Letters, 28:53–54,

    work page doi:10.1007/s00454-001-0047-6 2001

  15. [15]

    45 Daniël Paulusma, Christophe Picouleau, and Bernard Ries

    doi: 10.1016/0020-0190(88)90143-3. 45 Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Critical vertices and edges inH-free graphs.Discrete Applied Mathematics, 257:361–367, 2019.doi:10.1016/j.dam.2018.08.016. 46 Ana Silva. Graphs with small fall-spectrum.Discrete Applied Mathematics, 254:183–188,

    work page doi:10.1016/0020-0190(88)90143-3 2019

  16. [16]

    47 Jan Arne Telle

    doi:10.1016/j.dam.2018.06.037. 47 Jan Arne Telle. Characterization of domination-type parameters in graphs.Congressus Numerantium, 94:9–16,

    work page doi:10.1016/j.dam.2018.06.037 2018

  17. [17]

    On theb-coloring ofP4-tidy graphs.Discrete Applied Mathematics, 159:60–68, 2011.doi:10.1016/j.dam.2010.10.002

    49 Clara Inés Betancur Velasquez, Flavia Bonomo, and Ivo Koch. On theb-coloring ofP4-tidy graphs.Discrete Applied Mathematics, 159:60–68, 2011.doi:10.1016/j.dam.2010.10.002. 50 Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs.SIAM Journal on Applied Mathematics, 38(3):364–372, 1980.doi:10.1137/0138030

    work page doi:10.1016/j.dam.2010.10.002 2011