pith. sign in

arxiv: 2604.24343 · v1 · submitted 2026-04-27 · 💻 cs.DS

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs

Pawe{\l} Rafa{\l} Bieli\'nski , Marta Piecyk , Pawe{\l} Rz\k{a}\.zewski This is my paper

Pith reviewed 2026-05-08 01:31 UTC · model grok-4.3

classification 💻 cs.DS
keywords ordered graphsinduced subgraphsmaximum weight independent setcomputational complexitydichotomyquasipolynomial timeNP-hardnesshereditary classes
0
0 comments X

The pith

For every ordered graph H, MWIS on H-free ordered graphs is polynomial, quasipolynomial, subexponential, or NP-hard, with subexponential time only for one specific family of H.

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

The paper classifies the complexity of Maximum Weight Independent Set in ordered graphs that exclude any single ordered graph H as an induced subgraph. It establishes that the problem always falls into one of four categories: polynomial time, quasipolynomial time, subexponential time, or NP-hard. The subexponential case occurs exclusively for a well-structured family of H obtained from two nested edges by adding isolated vertices in a specific pattern. This produces an almost complete dichotomy separating the quasipolynomially solvable cases from the NP-hard ones in these hereditary classes of ordered graphs. A reader cares because the fixed linear ordering on vertices lets the authors draw a sharper boundary between tractable and intractable instances than is possible in ordinary graphs.

Core claim

The authors prove that for every ordered graph H, the Maximum Weight Independent Set problem on ordered graphs excluding H as an induced subgraph is solvable in polynomial time, quasipolynomial time, subexponential time, or is NP-hard. The subexponential case arises only for one well-structured family of forbidden graphs H, namely those obtained from two nested edges by adding isolated vertices in a specific way. As a direct consequence, apart from this family the problem is either solvable in quasipolynomial time or NP-hard, yielding an almost complete complexity dichotomy for MWIS in hereditary classes of ordered graphs defined by a single forbidden induced subgraph.

What carries the argument

The forbidden ordered graph H, whose structural form (specifically membership in the two-nested-edges family with prescribed isolated vertices) determines whether MWIS is polynomial, quasipolynomial, subexponential, or NP-hard.

Load-bearing premise

The input consists of ordered graphs whose linear vertex ordering is fixed and given as part of the instance, and the hereditary class is defined by excluding exactly one ordered graph H as an induced subgraph.

What would settle it

An ordered graph H outside the two-nested-edges-plus-isolates family for which MWIS on H-free ordered graphs admits neither a quasipolynomial-time algorithm nor an NP-hardness proof, or conversely an H inside that family for which the problem requires super-quasipolynomial yet subexponential time.

Figures

Figures reproduced from arXiv: 2604.24343 by Marta Piecyk, Pawe{\l} Rafa{\l} Bieli\'nski, Pawe{\l} Rz\k{a}\.zewski.

Figure 1
Figure 1. Figure 1: Sets XI j−1 , XI j , XI j+1, and independent sets I1, I2 (each of size k) in Claim 3.10.1. The orange subgraph cannot be induced, as otherwise, together with I1 and I2, it creates the forbidden structure. u ∗ v ∗ Y ′ j−1 Y ′ j Y ′ j+1 E1 E2 view at source ↗
Figure 2
Figure 2. Figure 2: Consecutive sets Y ′ j−1 , Y ′ j , and Y ′ j+1 in the proof of Claim 3.10.2. Orange, green, and black edges denote, respec￾tively, the edges of E1, the edges of E2, and the remaining edges. Thick nodes denote vertices of Se, and blue nodes denote vertices taken to U for k = 3. Construction of ZY . Fix some (Y, ℓ) ∈ Y. Now in time n O(log n) we will construct a family ZY of pairs (Z, ℓ′ ), where Z is a refi… view at source ↗
Figure 3
Figure 3. Figure 3: Sets XI 1 , XI 2 , XI r , and independent sets I1, I2 in the proof of Claim 3.10.3. The orange subgraph cannot be induced, as otherwise, together with I1 and I2, it creates the forbidden structure. We add the pair (X I , w(I)) to Y. Similarly as in the previous case, we have |Y| = O(n 2k ), and α(X ) = max (X I ,ℓI )∈Y α(X I ) + ℓ I . Now, we have the following analogue of Claim 3.10.1. Claim 3.10.3. Let(X… view at source ↗
Figure 4
Figure 4. Figure 4: Sets Y ′ 1 , Y ′ 2 , and Y ′ r in the proof of Claim 3.10.4. Orange, green, and black edges denote, respectively, the edges of E1, the edges of E2, and the remaining edges. Thick nodes denote the vertices of Se, and blue ones denote the vertices of U (in this example, for k ≥ 1, we have U = {u ∗}). the choice of v ∗ . We observe that the set N[U ∪ {v ∗ , v′}] intersects all the edges of E1. Indeed, suppose… view at source ↗
Figure 5
Figure 5. Figure 5: Sets Q′ 1 , . . . , Q′ r forming a chain Q′ in the proof of Theorem 3.9. Dotted blocks denote empty sets. Blocks in orange, blue, and green represent, respectively, the sets that belong to V1, V2, and V3. Step 1. Branching on high-degree vertices. First, we perform a standard branching on high-degree vertices. If there is a vertex v of degree at least τ , we branch on including or not including v in the so… view at source ↗
Figure 6
Figure 6. Figure 6: The graph constructed in the proof of Theorem 4.1. Underscored segments indicate blocks, with the two literal view at source ↗
Figure 7
Figure 7. Figure 7: The ordering of G(2) in the proof of Theorem 4.2. In all figures in this section we use the following convention. Gray box represents segment occupied by the core vertices. The dashed edge is present in G, but is replaced by a four-vertex path in G(2). This path is depicted in black, with some other such paths in grey. The dummy vertices fill segments represented by white boxes. Within any white box, they … view at source ↗
Figure 8
Figure 8. Figure 8: The ordering of G(2) in the proof of Theorem 4.3 view at source ↗
Figure 9
Figure 9. Figure 9: The ordering of G(2) in the proof of Theorem 4.4. Proof of Claim 4.3.2: Suppose G(2) contains a copy of one of the listed subgraphs, and let a ≺ b ⪯ c ≺ d ≺ e be the consecutive vertices of that copy. Note that b = c precisely when the subgraph has four vertices. Since b has a left neighbor, it must be a dummy vertex. Therefore any vertex that follows b, i.e., c, d, e, is a dummy as well. However, the only… view at source ↗
Figure 10
Figure 10. Figure 10: The ordering of G(2) in the proof of Theorem 4.5. Proof of Claim 4.5.1: Suppose that G(2) contains a copy of as a subgraph, and let a, b, c, d be the consecutive vertices of in that copy. Since b has a left neighbor, it is not a core vertex. Neither is c, as it follows b. Moreover, c has a right neighbor, so it must be the left dummy ℓe of some edge e of G. Therefore d is the right dummy re. Observe that … view at source ↗
Figure 11
Figure 11. Figure 11: A layer Ve, containing the path Ωe, in G1 (up) and G2 (down) as in the proof of Theorem 4.6. It remains to prove that G2 is -subgraph-free. We again first prove the following observation on the long edges in G2. Claim 4.6.5. Let xy and x ′y ′ be long edges of G2 such that x and x ′ belong to the same layer, and x ≺ y, x ′ ≺ y ′ , and x ≺ x ′ , and all vertices x, x′ , y, y′ are distinct. Then y ′ ≺ y. Pro… view at source ↗
Figure 12
Figure 12. Figure 12: The locomotive and two cabooses used in the proof of Theorem 4.12. In this and subsequent figures, underscoring view at source ↗
Figure 13
Figure 13. Figure 13: An interchangeable pair described in Lemma 4.13. view at source ↗
Figure 14
Figure 14. Figure 14: Permutation gadgets for elementary swaps used to prove Lemma 4.11. Boxes indicate canonical segments other view at source ↗
read the original abstract

The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices. Such an approach allows us to investigate the boundary of tractability more closely. However, most results so far concern coloring problems. In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs. For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases: (1) solvable in polynomial time, (2) solvable in quasipolynomial time, (3) solvable in subexponential time, (4) NP-hard. Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way. Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard.

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 manuscript classifies the complexity of Maximum Weight Independent Set (MWIS) on ordered graphs excluding a single ordered graph H as an induced subgraph. For every such H the problem falls into one of four regimes: polynomial-time solvable, quasipolynomial-time solvable, subexponential-time solvable (only for the specific family obtained from two nested edges by adding isolated vertices in a prescribed manner), or NP-hard. The result is presented as yielding an almost-complete dichotomy between the quasipolynomial and NP-hard cases.

Significance. If the classification is correct, the paper supplies a fine-grained complexity map for MWIS in hereditary classes of ordered graphs defined by a single forbidden induced ordered subgraph. This extends the existing literature on ordered graphs (previously focused mainly on coloring) and isolates the subexponential case to a single, explicitly described family, which is a structurally clean outcome. The work thereby sharpens the boundary between tractable and intractable regimes for this problem.

minor comments (3)
  1. [Abstract] Abstract, final sentence: the claim of a 'complete classification into four cases' is immediately followed by 'almost complete complexity dichotomy'; this tension should be resolved by a precise statement of what, if anything, remains open after the four-way partition.
  2. [Introduction] The formal definition of the 'two nested edges plus isolates' family (the sole subexponential case) appears only in the abstract; an early figure or a self-contained definition in Section 1 would improve readability for readers who wish to verify membership of a given H.
  3. [Preliminaries] Notation for ordered graphs and induced subgraphs is introduced gradually; a single consolidated notation paragraph or table at the beginning of the preliminaries would reduce cross-referencing.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the summary of our classification results and the significance statement. The recommendation for minor revision is noted. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a structural complexity classification of MWIS on ordered graphs excluding a single induced ordered subgraph H. The stated dichotomy (P, quasipolynomial, subexponential only for one explicit family of nested-edge-plus-isolates H, or NP-hard) is derived from case analysis on the structure of H rather than from any fitted parameter, self-defined quantity, or load-bearing self-citation that reduces the result to its own inputs. No equations, ansatzes, or predictions appear in the abstract or described claim; the classification is presented as a direct enumeration of cases. This matches the default expectation for a non-circular theoretical dichotomy in algorithmic graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result relies on standard assumptions of complexity theory (P vs NP, existence of subexponential algorithms) and on the definition of ordered graphs and induced subgraphs; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard complexity-theoretic assumptions (P ≠ NP, subexponential time classes are distinct from polynomial and NP-hard regimes)
    Invoked implicitly when assigning problems to the four complexity buckets.
  • domain assumption Ordered graphs are graphs with a fixed linear vertex ordering; induced subgraphs respect both edges and the ordering.
    Central to the definition of the hereditary classes under study.

pith-pipeline@v0.9.0 · 5550 in / 1448 out tokens · 46448 ms · 2026-05-08T01:31:43.733374+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

45 extracted references · 45 canonical work pages

  1. [1]

    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, and Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method.SIAM J. Comput., 53(3):624–647, 2024

    work page 2024

  2. [2]

    Lima, Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh, and Roohani Sharma

    Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh, and Roohani Sharma. Odd Cycle Transversal onP 5-free graphs in polynomial time.ACM Trans. Algorithms, 21(2):16:1–16:14, 2025

    work page 2025

  3. [3]

    Alekseev

    Vladimir E. Alekseev. The effect of local constraints on the complexity of determination of the graph independence number.Combinatorial-algebraic methods in applied mathematics, pages 3–13, 1982

    work page 1982

  4. [4]

    Chromatic number of ordered graphs with forbidden ordered subgraphs.Comb., 38(5):1021–1043, 2018

    Maria Axenovich, Jonathan Rollin, and Torsten Ueckerdt. Chromatic number of ordered graphs with forbidden ordered subgraphs.Comb., 38(5):1021–1043, 2018

    work page 2018

  5. [5]

    Subexponential-time algorithms for maximum independent set inP t-free and broom-free graphs.Algorithmica, 81(2):421–438, 2019

    Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen. Subexponential-time algorithms for maximum independent set inP t-free and broom-free graphs.Algorithmica, 81(2):421–438, 2019

    work page 2019

  6. [6]

    Ramsey numbers of ordered graphs.Electron

    Martin Balko, Josef Cibulka, Karel Král, and Jan Kyncl. Ramsey numbers of ordered graphs.Electron. J. Comb., 27(1):1, 2020

    work page 2020

  7. [7]

    Bernhart and Paul C

    Frank R. Bernhart and Paul C. Kainen. The book thickness of a graph.Journal of Combinatorial Theory, Series B, 27(3):320–331, 1979

    work page 1979

  8. [8]

    Saturation of ordered graphs.SIAM J

    Vladimir Bošković and Balázs Keszegh. Saturation of ordered graphs.SIAM J. Discret. Math., 37(2):1118–1141, 2023

    work page 2023

  9. [9]

    Maximum weight independent set forℓclaw-free graphs in polynomial time

    Andreas Brandstädt and Raffaele Mosca. Maximum weight independent set forℓclaw-free graphs in polynomial time. Discret. Appl. Math., 237:57–64, 2018

    work page 2018

  10. [10]

    Coloring ordered graphs with excluded induced ordered matchings

    Marcin Briański, James Davies, and Bartosz Walczak. Coloring ordered graphs with excluded induced ordered matchings. Banff International Research Station. 22w5009: Extremal Combinatorics and Ge- ometry.https://www.birs.ca/events/2022/5-day-workshops/22w5009/videos/watch/ 202208161436-Walczak.html, 2022

    work page 2022

  11. [11]

    From Gap-Exponential Time Hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.SIAM J

    Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-Exponential Time Hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.SIAM J. Comput., 49(4):772–810, 2020. 32

    work page 2020

  12. [12]

    Planar permutation graphs.Annales de l’institut Henri Poincaré, 6(4):433–438, 1967

    Gary Chartrand and Frank Harary. Planar permutation graphs.Annales de l’institut Henri Poincaré, 6(4):433–438, 1967

    work page 1967

  13. [13]

    Finding largeH-colorable subgraphs in hereditary graph classes.SIAM J

    Maria Chudnovsky, Jason King, Michal Pilipczuk, Paweł Rzążewski, and Sophie Spirkl. Finding largeH-colorable subgraphs in hereditary graph classes.SIAM J. Discret. Math., 35(4):2357–2386, 2021

    work page 2021

  14. [14]

    Sparse induced subgraphs inP 6-free graphs

    Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Sparse induced subgraphs inP 6-free graphs. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 5291–5299. SIAM, 2024

    work page 2024

  15. [15]

    Ordered Ramsey numbers.J

    David Conlon, Jacob Fox, Choongbum Lee, and Benny Sudakov. Ordered Ramsey numbers.J. Comb. Theory B, 122:353– 383, 2017

    work page 2017

  16. [16]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

    work page 2015

  17. [17]

    Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski

    Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. On cycle transversals and their connected variants in the absence of a small linear forest.Algorithmica, 82(10):2841–2866, 2020

    work page 2020

  18. [18]

    Faster 3-Coloring of small-diameter graphs.SIAM J

    Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of small-diameter graphs.SIAM J. Discret. Math., 36(3):2205–2224, 2022

    work page 2022

  19. [19]

    Ordered unavoidable sub-structures in matchings and random matchings.Electron

    Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński. Ordered unavoidable sub-structures in matchings and random matchings.Electron. J. Comb., 31(2), 2024

    work page 2024

  20. [20]

    Lima, Andrea Munaro, and Amir Nikabadi

    Esther Galby, Paloma T. Lima, Andrea Munaro, and Amir Nikabadi. Maximum Listr-Colorable Induced Subgraphs in kP3-free graphs. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors,33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025, LIPIcs, pages 40:1–40:13. Schloss Dagstuhl - Leibniz-Zentrum f...

    work page 2025

  21. [21]

    Garey, David S

    Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems.Theoretical Computer Science, 1(3):237–267, 1976

    work page 1976

  22. [22]

    Independent set onP k-free graphs in quasi-polynomial time

    Peter Gartland and Daniel Lokshtanov. Independent set onP k-free graphs in quasi-polynomial time. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020

    work page 2020

  23. [23]

    Maxi- mum weight independent set in graphs with no long claws in quasi-polynomial time

    Peter Gartland, Daniel Lokshtanov, Tomás Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Maxi- mum weight independent set in graphs with no long claws in quasi-polynomial time. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, J...

    work page 2024

  24. [24]

    Finding large induced sparse subgraphs inC >t-free graphs in quasipolynomial time

    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Finding large induced sparse subgraphs inC >t-free graphs in quasipolynomial time. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 330–341. ...

    work page 2021

  25. [25]

    Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.SIAM J

    Fanica Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.SIAM J. Comput., 1(2):180–187, 1972

    work page 1972

  26. [26]

    Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnnals of Discrete Mathematics

    Martin C. Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnnals of Discrete Mathematics. Elsevier/North-Holland, 2nd edition, 2004

    work page 2004

  27. [27]

    Polynomial-time algorithm for maximum weight independent set onP 6-free graphs.ACM Trans

    Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for maximum weight independent set onP 6-free graphs.ACM Trans. Algorithms, 18(1):4:1–4:57, 2022

    work page 2022

  28. [28]

    List-3-Coloring ordered graphs with a forbidden induced subgraph.SIAM J

    Sepehr Hajebi, Yanjia Li, and Sophie Spirkl. List-3-Coloring ordered graphs with a forbidden induced subgraph.SIAM J. Discret. Math., 38(1):1158–1190, 2024

    work page 2024

  29. [29]

    Clique is hard to approximate withinn (1−ε).Electron

    Johan Håstad. Clique is hard to approximate withinn (1−ε).Electron. Colloquium Comput. Complex., TR97, 1997

    work page 1997

  30. [30]

    Heath, F

    Lenwood S. Heath, F. Thomson Leighton, and Arnold L. Rosenberg. Comparing queues and stacks as mechanisms for laying out graphs.SIAM Journal on Discrete Mathematics, 5(3):398–412, 1992. 33

    work page 1992

  31. [31]

    Heath and Arnold L

    Lenwood S. Heath and Arnold L. Rosenberg. Laying out graphs using queues.SIAM J. Comput., 21(5):927–958, 1992

    work page 1992

  32. [32]

    Which problems have strongly exponential complexity?J

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity?J. Comput. Syst. Sci., 63(4):512–530, 2001

    work page 2001

  33. [33]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972

    work page 1972

  34. [34]

    On the Turán number of ordered forests.J

    Dániel Korándi, Gábor Tardos, István Tomon, and Craig Weidert. On the Turán number of ordered forests.J. Comb. Theory A, 165:32–43, 2019

    work page 2019

  35. [35]

    Improved hardness of approximatingk-Clique under ETH

    Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. Improved hardness of approximatingk-Clique under ETH. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 285–306. IEEE, 2023

    work page 2023

  36. [36]

    Plummer.Matching Theory, volume 121 ofNorth–Holland Mathematics Studies

    László Lovász and Michael D. Plummer.Matching Theory, volume 121 ofNorth–Holland Mathematics Studies. North–Holland, Amsterdam – New York – Oxford – Tokyo, 1986

    work page 1986

  37. [37]

    Lozin and Martin Milanič

    Vadim V. Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.J. Discrete Algorithms, 6(4):595–604, 2008

    work page 2008

  38. [38]

    Erdős-Hajnal-type results for monotone paths.J

    János Pach and István Tomon. Erdős-Hajnal-type results for monotone paths.J. Comb. Theory B, 151:21–37, 2021

    work page 2021

  39. [39]

    Forbidden paths and cycles in ordered graphs and matrices.Israel Journal of Mathematics, 155(1):359–380, December 2006

    János Pach and Gábor Tardos. Forbidden paths and cycles in ordered graphs and matrices.Israel Journal of Mathematics, 155(1):359–380, December 2006

    work page 2006

  40. [40]

    Feedback Vertex Set and Even Cycle Transversal forH-free graphs: Finding large block graphs.SIAM J

    Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal forH-free graphs: Finding large block graphs.SIAM J. Discret. Math., 36(4):2453–2472, 2022

    work page 2022

  41. [41]

    List coloring ordered graphs with forbidden induced subgraphs

    Marta Piecyk and Paweł Rzążewski. List coloring ordered graphs with forbidden induced subgraphs. In Meena Ma- hajan, Florin Manea, Annabelle McIver, and Kim Thang Nguyen, editors,43rd International Symposium on Theoretical Aspects of Computer Science, STACS 2026, Grenoble, France, March 9-13, 2026, LIPIcs, pages 74:1–74:17. Schloss Dagstuhl - Leibniz-Zent...

    work page 2026

  42. [42]

    Quasi-polynomial-time algorithm for independent set in Pt-free graphs via shrinking the space of induced paths

    Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzą ˙ewski. Quasi-polynomial-time algorithm for independent set in Pt-free graphs via shrinking the space of induced paths. In Hung Viet Le and Valerie King, editors,4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204–209. SIAM, 2021

    work page 2021

  43. [43]

    A note on stable sets and colorings of graphs.Commentationes Mathematicae Universitatis Carolinae, 15:307–309, 1974

    Svatopluk Poljak. A note on stable sets and colorings of graphs.Commentationes Mathematicae Universitatis Carolinae, 15:307–309, 1974

    work page 1974

  44. [44]

    Seymour, and Sophie Spirkl

    Alex Scott, Paul D. Seymour, and Sophie Spirkl. Pure pairs VI: Excluding an ordered tree.SIAM J. Discret. Math., 36(1):170–187, 2022

    work page 2022

  45. [45]

    Extremal theory of vertex or edge ordered graphs

    Gábor Tardos. Extremal theory of vertex or edge ordered graphs. In Allan Lo, Richard Mycroft, Guillem Perarnau, and Andrew Treglown, editors,Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Conference, Birmingham, UK, July 29 - August 2, 2019, pages 221–236. Cambridge University Press, 2019. 34

    work page 2019