pith. sign in

arxiv: 2604.06999 · v1 · submitted 2026-04-08 · 🧮 math.CO · cs.DM

Vertex-critical graphs in subfamilies of (P₄+ell P₁)-free graphs

Iain Beaton , Ben Cameron This is my paper

Pith reviewed 2026-05-10 17:41 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords vertex-critical graphs(P4 + lP1)-free graphschromatic numberforbidden induced subgraphsgraph coloring algorithmsfiniteness resultshereditary graph classes
0
0 comments X

The pith

There are only finitely many k-vertex-critical graphs in several subfamilies of (P4 + ℓP1)-free graphs for every k.

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

The paper proves finiteness of k-vertex-critical members in three concrete subfamilies of (P4 + ℓP1)-free graphs: those that additionally forbid the chair, those that forbid both P5 and the bull, and those that forbid both P5 and the cricket. A more general result covers all these cases by showing that forbidding B4(m) and B3(m)+ alongside (P4 + ℓP1) leaves only finitely many such critical graphs for any fixed k, ℓ, and m. Because the k-colorability decision problem is polynomial-time solvable once the finite list of critical obstructions is known, the results immediately yield simple certifying algorithms for coloring graphs in each of these classes. The authors also strengthen the known chromatic-number bounds, proving χ(G) ≤ ℓ + 2 when the graphs are triangle-free and a general O(ℓ^{ω-1}) bound for arbitrary (P4 + ℓP1)-free graphs.

Core claim

For every k ≥ 1 and every ℓ, m ≥ 0 the class of (P4 + ℓP1, B4(m), B3(m)+)-free graphs contains only finitely many k-vertex-critical graphs. The three listed families are obtained by choosing appropriate m so that the extra forbidden graphs (chair, bull, cricket) become special cases of B4(m) or B3(m)+. The same finiteness supplies polynomial-time certifying algorithms for deciding whether any graph in these classes is k-colorable.

What carries the argument

The general finiteness theorem for (P4 + ℓP1, B4(m), B3(m)+)-free graphs, where B_n(m) is formed by attaching a star K_{1,m} to one end of a path on n vertices and B_n(m)+ augments it by identifying an edge of a triangle with a degree-2 / degree-m edge of B_n(m).

If this is right

  • Polynomial-time certifying algorithms decide k-colorability for every fixed k in each of the listed families.
  • χ(G) ≤ ℓ + 2 holds for all (P4 + ℓP1, K3)-free graphs.
  • A general χ-bound of O(ℓ^{ω-1}) holds for arbitrary (P4 + ℓP1)-free graphs.

Where Pith is reading between the lines

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

  • The same structural restrictions may force finiteness in other combinations of forbidden subgraphs that contain the chair, bull, or cricket as induced subgraphs.
  • The improved χ-bounds suggest that the (P4 + ℓP1)-free class itself may admit tighter coloring bounds once triangle-free members are handled separately.
  • The certifying algorithms could be made practical by computing the finite obstruction sets for small k.

Load-bearing premise

The extra forbidden subgraphs B4(m) and B3(m)+ (or the chair, bull, and cricket) impose enough structural control on (P4 + ℓP1)-free graphs that infinite families of k-vertex-critical graphs cannot exist.

What would settle it

An explicit infinite family of k-vertex-critical graphs that remain (P4 + ℓP1, B4(m), B3(m)+)-free for some fixed k, ℓ, m would disprove the claim.

Figures

Figures reproduced from arXiv: 2604.06999 by Ben Cameron, Iain Beaton.

Figure 1
Figure 1. Figure 1: Graphs H of order 5 where the finiteness of k-vertex-critical (P5, H)-free graphs is unknown. Note that the finiteness of |critk(P5, P4 + P1)| is not known for any k ≥ 5, thus linking interest in the two open problems discussed above. In this paper, we provide the first results on k-vertex-critical (P4 + ℓP1, H)-free graphs for ℓ > 1 and, in fact, all of our results hold for all ℓ ≥ 0. To state our results… view at source ↗
Figure 2
Figure 2. Figure 2: The forbidden induced graphs in Theorems 1 and Corollary 1 We are now ready to state the two main results of our paper, and discuss some corollaries. Theorem 1. For all k ≥ 1 and ℓ, m ≥ 0, |critk(P4 + ℓP1, B4(m), B3(m) +)| < ∞. Theorem 2. For all k ≥ 1 and ℓ ≥ 0, |critk(P4 + ℓP1, 2P2)| < ∞. Despite its generality, we give a very short and easy to follow proof of Theo￾rem 1. We achieve this by a new technic… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of G in proof of Theorem 1 Let S ′ be the set S \ N(x ′ ). If |S ′ | ≥ ℓ, then {z, x, x′ , s1} ∪ S ′ induces a graph containing an induced P4 + ℓP1 if z ≁ x ′ and {y, z, x′ , s1} ∪ S ′ induces a graph containing an induced P4 + ℓP1 if z ∼ x ′ . Therefore, |S ′ | ≤ ℓ − 1, and |N(x ′ ) ∩ S| ≥ c − ℓ + 1 = m. Now, the union of {y, z, x, x′} and any subset of S containing m neighbours of x ′ induce… view at source ↗
read the original abstract

A graph $G$ is $k$-vertex-critical if $\chi(G)=k$ but $\chi(G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell\ge 0$: $\bullet$ $(P_4+\ell P_1,\text{chair})$-free graphs, $\bullet$ $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and $\bullet$ $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs. In fact, all but the first of these are special cases of our general result that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,B_{4}(m),B_{3}(m)^{+})$-free graphs for all $k\ge 1$ and $\ell,m\ge 0$. Here $B_{n}(m)$ is the graph obtained from a path of order $n$ by identifying one of its leaves with the centre vertex of $K_{1,m}$ and $B_{n}(m)^{+}$ is the graph obtained by identifying an edge of $K_3$ with the edge of $B_{n}(m)$ with endpoints of degrees $2$ and $m$, respectively. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$. We also show that $\chi(G)\le \ell+2$ for all $(P_4+\ell P_1,K_3)$-free graphs and all $\ell\ge 0$, improving the previously known upper bound of $2\ell+2$ that followed from Randerath and Schiermeyer's 2004 result on $(P_t,K_3)$-free graphs. More generally, we provide a $\chi$-bound in $O(\ell^{\omega-1})$ for $(P_4+\ell P_1)$-free graphs which improves the bound of $(2\ell+2)^{\omega-1}$ which followed from Gravier, Ho\`ang and Maffray in 2003 for $P_{t}$-free graphs.

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

0 major / 3 minor

Summary. The paper proves finiteness of the set of k-vertex-critical graphs for every fixed k ≥ 1 in three subfamilies of (P_4 + ℓ P_1)-free graphs: those that additionally forbid the chair, those that forbid P_5 and the bull, and those that forbid P_5 and the cricket. These are recovered as special cases of the general theorem that (P_4 + ℓ P_1, B_4(m), B_3(m)^+)-free graphs have only finitely many k-vertex-critical members for any ℓ, m ≥ 0. The manuscript also establishes the bound χ(G) ≤ ℓ + 2 for all (P_4 + ℓ P_1, K_3)-free graphs (improving the earlier 2ℓ + 2 bound) and the general bound O(ℓ^{ω-1}) for (P_4 + ℓ P_1)-free graphs.

Significance. The finiteness theorems supply concrete structural restrictions (via reductions that bound degree and eliminate certain path configurations) that imply polynomial-time certifying algorithms for k-colorability in each listed class. The explicit lemmas showing that the bull and cricket appear as induced subgraphs of B_4(m) for large m, together with the separate chair argument, give a uniform method that may extend to the full (P_4 + ℓ P_1)-free class. The chromatic-number improvements are quantitative and directly strengthen earlier results of Randerath–Schiermeyer and Gravier–Hoàng–Maffray.

minor comments (3)
  1. Abstract: the precise edge-identification used to form B_n(m)^+ from B_n(m) and K_3 is stated but would benefit from an accompanying diagram or one-sentence expansion for readers unfamiliar with the notation.
  2. Section containing the general finiteness theorem: the reduction eliminating high-degree vertices is load-bearing; a short statement of the resulting order bound in terms of k, ℓ and m would make the dependence explicit.
  3. χ-bound section: the inductive coloring argument for the (P_4 + ℓ P_1, K_3)-free case is described at a high level; inserting the precise induction hypothesis (e.g., every proper subgraph is (ℓ+1)-colorable) would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its significance in providing finiteness results for k-vertex-critical graphs in the specified subfamilies, and the recommendation for minor revision. We appreciate the connections drawn to certifying algorithms and prior chromatic bounds.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds via explicit structural lemmas that bound the order of k-vertex-critical graphs by eliminating high-degree vertices and forbidden path configurations in the presence of the additional subgraphs (chair; B4(m), B3(m)+). The general finiteness theorem for (P4+ℓP1, B4(m), B3(m)+)-free graphs is established first by these reductions; bull and cricket cases then follow directly from showing they appear as induced subgraphs of the B families for large m, while the chair case uses a separate but analogous argument. The χ ≤ ℓ+2 bound for (P4+ℓP1, K3)-free graphs is obtained by an inductive coloring procedure that exploits triangle-freeness and the limited P4+isolates structure. These steps are combinatorial and self-contained; they do not reduce by definition or construction to the claimed conclusions, nor rely on load-bearing self-citations or fitted inputs renamed as predictions. Prior bounds from Randerath-Schiermeyer and Gravier-Hoàng-Maffray are cited only for comparison, not as the foundation of the new results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies entirely on standard definitions and combinatorial arguments from graph theory; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Standard axioms of graph theory: graphs are finite undirected simple structures, chromatic number is the minimum colors needed for proper vertex coloring, and vertex-criticality is defined via deletion of single vertices.
    All claims rest on these background definitions invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5803 in / 1493 out tokens · 114970 ms · 2026-05-10T17:41:21.039144+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

43 extracted references · 43 canonical work pages

  1. [1]

    Discrete Appl

    Abuadas, T., Cameron, B., Hoàng, C.T., Sawada, J.: Vertex-critical (P3 +ℓP 1)-free and vertex-critical (gem, co-gem)-free graphs. Discrete Appl. Math.344, 179–187 (2024).https://doi.org/https://doi.org/ 10.1016/j.dam.2023.11.042

    work page doi:10.1016/j.dam.2023.11.042 2024

  2. [2]

    The- oretical Computer Science1042, 115234 (2025).https://doi.org/https: //doi.org/10.1016/j.tcs.2025.115234

    Beaton, I., Cameron, B.: Vertex-critical graphs in co-gem-free graphs. The- oretical Computer Science1042, 115234 (2025).https://doi.org/https: //doi.org/10.1016/j.tcs.2025.115234

    work page doi:10.1016/j.tcs.2025.115234 2025

  3. [3]

    SIAM (1999)

    Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM (1999)

    work page 1999

  4. [4]

    Discrete Appl

    Brause, C., Geißer, M., Schiermeyer, I.: Homogeneous sets, clique- separators, critical graphs, and optimalχ-binding functions. Discrete Appl. Math.320, 211–222 (2022).https://doi.org/https://doi.org/ 10.1016/j.dam.2022.05.014

    work page doi:10.1016/j.dam.2022.05.014 2022

  5. [5]

    In: Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings

    Cai, Q., Huang, S., Li, T., Shi, Y.: Vertex-critical(P5, banner)-free graphs. In: Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings. vol. 11458, pp. 111–120. Springer (2019)

    work page 2019

  6. [6]

    Discrete Appl

    Cai, Q., Goedgebeur, J., Huang, S.: Some results onk-criticalP 5-free graphs. Discrete Appl. Math.334, 91–100 (2023).https://doi.org/ https://doi.org/10.1016/j.dam.2023.03.008

    work page doi:10.1016/j.dam.2023.03.008 2023

  7. [7]

    Discrete Appl

    Cameron, B., Hoàng, C.T., Sawada, J.: Dichotomizingk-vertex-criticalH- free graphs forHof order four. Discrete Appl. Math.312, 106–115 (2022). https://doi.org/https://doi.org/10.1016/j.dam.2021.11.001

    work page doi:10.1016/j.dam.2021.11.001 2022

  8. [8]

    Cameron, B., Hoàng, C.T.: A refinement on the structure of vertex-critical (P5, gem)-free graphs. Theoret. Comput. Sci.961, 113936 (2023).https: //doi.org/https://doi.org/10.1016/j.tcs.2023.113936

    work page doi:10.1016/j.tcs.2023.113936 2023

  9. [9]

    Graphs Combin.40, 30 (2024)

    Cameron, B., Hoàng, C.T.: Infinite families ofk-vertex-critical(P5, C5)-free graphs. Graphs Combin.40, 30 (2024)

    work page 2024

  10. [10]

    Cameron, K., Goedgebeur, J., Huang, S., Shi, Y.:k-Critical graphs inP5- free graphs. Theoret. Comput. Sci.864, 80–91 (2021).https://doi.org/ https://doi.org/10.1016/j.tcs.2021.02.029

    work page doi:10.1016/j.tcs.2021.02.029 2021

  11. [11]

    preprint, arXiv:2509.14135 [math.CO] (2025)

    Chen, R., Wu, D., Zhang, X.: Structure, Perfect Divisibility and Coloring of(P 2 ∪P4, C 3)-Free Graphs. preprint, arXiv:2509.14135 [math.CO] (2025)

    work page arXiv 2025

  12. [12]

    Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring and list three-coloringH-free graphs. SIAM J. Discrete Math.34(1), 431–469 (2020)

    work page 2020

  13. [13]

    Combinatorica44(5), 1063–1068 (2024).https://doi.org/10

    Chudnovsky, M., Hajebi, S., Spirkl, S.: List-k-ColoringH-Free Graphs for Allk >4. Combinatorica44(5), 1063–1068 (2024).https://doi.org/10. 1007/s00493-024-00106-2

    work page 2024

  14. [14]

    Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. of Math.164(1), 51–229 (2006).https: //doi.org/10.4007/annals.2006.164.51 Vertex-critical graphs in subfamilies of(P4 +ℓP 1)-free graphs 13

    work page doi:10.4007/annals.2006.164.51 2006

  15. [15]

    Chudnovsky, M., Spirkl, S., Zhong, M.: Four-ColoringP6-Free Graphs. I. Extending an Excellent Precoloring. SIAM Journal on Computing53(1), 111–145 (2024),https://doi.org/10.1137/18M1234837

    work page doi:10.1137/18m1234837 2024

  16. [16]

    Chudnovsky, M., Spirkl, S., Zhong, M.: Four-ColoringP6-Free Graphs. II. Finding an Excellent Precoloring. SIAM Journal on Computing53(1), 146– 187 (2024),https://doi.org/10.1137/18M1234849

    work page doi:10.1137/18m1234849 2024

  17. [17]

    Algorithmica71(1), 21–35 (2015).https: //doi.org/10.1007/s00453-013-9777-0

    Couturier, J.F., Golovach, P.A., Kratsch, D., Paulusma, D.: List Coloring in the Absence of a Linear Forest. Algorithmica71(1), 21–35 (2015).https: //doi.org/10.1007/s00453-013-9777-0

    work page doi:10.1007/s00453-013-9777-0 2015

  18. [18]

    Discrete Appl

    Dhaliwal, H.S., Hamel, A.M., Hoàng, C.T., Maffray, F., McConnell, T.J.D., Panait, S.A.: On color-critical(P5,co-P5)-free graphs. Discrete Appl. Math. 216, 142–148 (2017).https://doi.org/10.1016/j.dam.2016.05.018

    work page doi:10.1016/j.dam.2016.05.018 2017

  19. [19]

    Discrete Mathematics272(2), 285–290 (2003).https://doi.org/https://doi.org/10.1016/S0012-365X(03) 00197-3,https://www.sciencedirect.com/science/article/pii/ S0012365X03001973

    Gravier, S., Hoàng, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Mathematics272(2), 285–290 (2003).https://doi.org/https://doi.org/10.1016/S0012-365X(03) 00197-3,https://www.sciencedirect.com/science/article/pii/ S0012365X03001973

    work page doi:10.1016/s0012-365x(03 2003

  20. [20]

    Hajebi, S., Li, Y., Spirkl, S.: Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph. SIAM J. Discrete Math.36(3), 2004–2027 (2022).https://doi.org/10.1137/21M1443352

    work page doi:10.1137/21m1443352 2004

  21. [21]

    Algorithmica57, 74–81 (2010).https://doi.org/10.1007/s00453-008-9197-8

    Hoàng, C.T., Kamiński, M., Lozin, V., Sawada, J., Shu, X.: Decidingk- colorability ofP 5-free graphs in polynomial time. Algorithmica57, 74–81 (2010).https://doi.org/10.1007/s00453-008-9197-8

    work page doi:10.1007/s00453-008-9197-8 2010

  22. [22]

    Discrete Appl

    Hoàng, C.T., Moore, B., Recoskie, D., Sawada, J., Vatshelle, M.: Construc- tions ofk-criticalP 5-free graphs. Discrete Appl. Math.182, 91–98 (2015). https://doi.org/10.1016/j.dam.2014.06.007

    work page doi:10.1016/j.dam.2014.06.007 2015

  23. [23]

    Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput.10(4), 718–720 (1981).https://doi.org/10.1137/0210055

    work page doi:10.1137/0210055 1981

  24. [24]

    Tree-depth, subgraph coloring and homomor- phism bounds

    Huang, S.: Improved complexity results onk-coloringPt-free graphs. Euro- pean J. Combin.51, 336–346 (2016).https://doi.org/10.1016/j.ejc. 2015.06.005

    work page doi:10.1016/j.ejc 2016

  25. [25]

    Discrete Appl

    Huang, S., Li, J., Xia, W.: Critical (P5, bull)-free graphs. Discrete Appl. Math.334, 15–25 (2023).https://doi.org/https://doi.org/10.1016/ j.dam.2023.02.019

    work page 2023

  26. [26]

    Discrete Appl

    Huang, S., Li, Z.: Vertex-Critical(P 5, chair)-free Graphs. Discrete Appl. Math.341, 9–15 (2023).https://doi.org/https://doi.org/10.1016/ j.dam.2023.07.014

    work page 2023

  27. [27]

    preprint, arXiv:2504.14134 [math.CO] (2025)

    Jua, Y., Jooken, J., Goedgebeur, J., Huang, S.: There are finitely many 5- vertex-critical (P6,bull)-free graphs. preprint, arXiv:2504.14134 [math.CO] (2025)

    work page arXiv 2025

  28. [28]

    Kamiński, M., Lozin, V.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math.2(1), 61–66 (2007).https: //doi.org/10.11575/cdm.v2i1.61890

    work page doi:10.11575/cdm.v2i1.61890 2007

  29. [29]

    Discrete Appl

    Kamiński, M., Pstrucha, A.: Certifying coloring algorithms for graphs without long induced paths. Discrete Appl. Math.261, 258–267 (2019). https://doi.org/10.1016/j.dam.2018.09.031 14 Iain Beaton and Ben Cameron

    work page doi:10.1016/j.dam.2018.09.031 2019

  30. [30]

    In: Complexity of computer computations (Proc

    Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972). pp. 85–103 (1972)

    work page 1972

  31. [31]

    Leven, D., Gail, Z.: NP completeness of finding the chromatic index of regular graphs. J. Algorithms4, 35–44 (1983)

    work page 1983

  32. [32]

    Maffray, F., Morel, G.: On3-colorableP 5-free graphs. SIAM J. Discrete Math.26(4), 1682–1708 (2012).https://doi.org/10.1137/110829222

    work page doi:10.1137/110829222 2012

  33. [33]

    McConnell, R., Mehlhorn, K., Näher, S., Schweitzer, P.: Certifying algo- rithms. Comput. Sci. Rev.5(2), 119–161 (2011).https://doi.org/https: //doi.org/10.1016/j.cosrev.2010.09.009

    work page doi:10.1016/j.cosrev.2010.09.009 2011

  34. [34]

    Discrete Math- ematics313(5), 715–720 (2013).https://doi.org/https://doi.org/10

    Pyatkin, A.V.: Triangle-free2P3-free graphs are4-colorable. Discrete Math- ematics313(5), 715–720 (2013).https://doi.org/https://doi.org/10. 1016/j.disc.2012.10.019

    work page 2013

  35. [35]

    Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. (s2-30), 264–286 (1928)

    work page 1928

  36. [36]

    Graphs Combin.20(1), 1–40 (2004).https://doi.org/10.1007/ s00373-003-0540-1

    Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs— a survey. Graphs Combin.20(1), 1–40 (2004).https://doi.org/10.1007/ s00373-003-0540-1

    work page 2004

  37. [37]

    Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27(1), 544–548 (1928).https://doi.org/10.1007/BF01171114

    work page doi:10.1007/bf01171114 1928

  38. [38]

    Journal of Graph Theory88(2), 312–336 (2018)

    Trotignon, N., Pham, L.A.:χ-bounds, operations, and chords. Journal of Graph Theory88(2), 312–336 (2018)

    work page 2018

  39. [39]

    Prentice Hall, Inc., Upper Sad- dle River, NJ (1996)

    West, D.B.: Introduction to Graph Theory. Prentice Hall, Inc., Upper Sad- dle River, NJ (1996)

    work page 1996

  40. [40]

    Xia, W., Jooken, J., Goedgebeur, J., Beaton, I., Cameron, B., Huang, S.: Vertex-Critical(P 5, W4)-FreeGraphs.In:Fomin,F.V.,Xiao,M.(eds.)Com- puting and Combinatorics. pp. 139–152. Springer Nature Singapore, Singa- pore (2026)

    work page 2026

  41. [41]

    Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Critical(P 5, dart)-Free Graphs. In: Combinatorial Optimization and Applications: 16th Interna- tional Conference, COCOA 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings,PartII.p.390–402.Springer-Verlag,Berlin,Heidelberg(2023), https://doi.org/10.1007/978-3-031-49614-1{_}29

    work page doi:10.1007/978-3-031-49614-1 2023

  42. [42]

    Theoretical Computer Science1051, 115411 (2025)

    Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Some Results on Critical (P5, H)-free Graphs. Theoretical Computer Science1051, 115411 (2025). https://doi.org/https://doi.org/10.1016/j.tcs.2025.115411

    work page doi:10.1016/j.tcs.2025.115411 2025

  43. [43]

    preprint, arXiv:2512.12349 [math.CO] (2025)

    Zhou, Y., Jooken, J., Shan, B., Goedgebeur, J., Huang, S.: Three- coloring triangle-free graphs without long forbidden paths. preprint, arXiv:2512.12349 [math.CO] (2025)

    work page arXiv 2025