Polynomial-time recognition and maximum independent set in Burling graphs

Bartosz Walczak; Pawe{\l} Rz\k{a}\.zewski

arxiv: 2407.16666 · v2 · submitted 2024-07-23 · 🧮 math.CO · cs.DM

Polynomial-time recognition and maximum independent set in Burling graphs

Pawe{\l} Rz\k{a}\.zewski , Bartosz Walczak This is my paper

Pith reviewed 2026-05-23 22:54 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords Burling graphsstrict frame representationpolynomial-time recognitionmaximum independent sethereditary graph classestriangle-free graphs

0 comments

The pith

Burling graphs can be recognized in polynomial time and their maximum independent set solved in polynomial time using a strict frame representation.

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

The paper gives a polynomial-time algorithm that takes an arbitrary graph and either determines it is not a Burling graph or produces a strict frame representation of it. Once the representation is in hand, the same paper shows that the size of a maximum independent set can also be computed in polynomial time. Burling graphs are hereditary, triangle-free, and can require arbitrarily many colors, so the result separates polynomial-time solvability of maximum independent set from the chi-boundedness property in hereditary classes.

Core claim

A Burling graph is an induced subgraph of a graph arising in Burling's triangle-free high-chromatic construction, equivalently a graph that admits a strict frame representation. The central claim is that there exists a polynomial-time algorithm which, given any graph, decides whether it is a Burling graph and, if so, constructs a strict frame representation; the representation in turn yields a polynomial-time algorithm for maximum independent set. As a direct consequence, Burling graphs become the first known hereditary class that admits polynomial-time maximum independent set yet is not chi-bounded.

What carries the argument

strict frame representation, the geometric object equivalent to membership in the Burling class and the structure that directly supplies the polynomial-time recognition and independent-set algorithms.

If this is right

Burling graphs admit a polynomial-time recognition algorithm.
Maximum independent set is solvable in polynomial time on every Burling graph.
Burling graphs supply the first hereditary class that is not chi-bounded yet has polynomial-time maximum independent set.

Where Pith is reading between the lines

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

The same recognition technique might be adaptable to decide membership in other geometrically defined hereditary classes built from similar frame or interval constructions.
If the frame representation also encodes clique or coloring information efficiently, it could separate additional optimization problems from chi-boundedness.
The result suggests that hereditary classes defined by forbidden induced subgraphs arising from geometric constructions may systematically admit efficient independent-set algorithms even when chromatic number is unbounded.

Load-bearing premise

Every Burling graph possesses a strict frame representation that can be constructed in polynomial time.

What would settle it

A concrete Burling graph on which the recognition procedure either fails to terminate in polynomial time or returns a representation that does not allow polynomial-time computation of the maximum independent set.

Figures

Figures reproduced from arXiv: 2407.16666 by Bartosz Walczak, Pawe{\l} Rz\k{a}\.zewski.

**Figure 1.** Figure 1: Strict family of frames: (a) required configuration of every intersecting pair of frames; (b)–(d) disallowed configurations. particular imply their χ-boundedness. Thomassé, Trotignon, and Vušković [16] asked whether every hereditary class of graphs that admits a polynomial-time algorithm for the maximum independent set problem is χ-bounded. Being able to construct a strict frame representation, we can solv… view at source ↗

**Figure 2.** Figure 2: Correspondence between the relations ≺ and ↷ in a Burling set and configurations of pairs of frames in its strict frame representation. a strict frame graph) and triangle-free (that is, no strict frame graph contains three pairwise adjacent vertices). A relation on a set S is a set R ⊆ S × S. We write x R y to denote that (x, y) ∈ R, and we write R|U for the relation R ∩ (U × U) on a subset U of S. A cycle… view at source ↗

**Figure 3.** Figure 3: Distinguished elements of a Burling set in a frame representation: a is a root, b and f are probes, and all three are exposed; c and d are exposed but neither roots not probes; e is not exposed. We complete this section with auxiliary definitions and lemmas on Burling sets. Lemma 4 ([12, Lemma 5.3]). In a Burling set (S, ≺, ↷), the relation ≺ ∪ ↷ is acyclic. Proof. Let R = ≺ ∪ ↷. Suppose R is not acyclic. … view at source ↗

**Figure 4.** Figure 4: The second condition in the algorithm for B(X, S) with C1 and C2 the components of S − {r}. consult [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 5.** Figure 5: A solution to a subproblem R(X, r, S). The graph induced by S−N(r) has six components C1, . . . , C6, of which C1 and C2 are inner while C3, . . . , C6 are outer. Gray areas are where particular components are represented. assume the former, without loss of generality. By Lemma 5, since r ⊀ x2, a path from x1 to r in C1 ∪ {r} must contain a vertex x such that x ↷ x2. This is a contradiction, because neithe… view at source ↗

read the original abstract

A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. Equivalently, a Burling graph is a graph that admits a so-called strict frame representation. We provide a polynomial-time algorithm to decide whether a given graph is a Burling graph and if it is, to construct its strict frame representation. The representation then enables a polynomial-time algorithm for the maximum independent set problem in Burling graphs. As a consequence, we establish Burling graphs as the first known hereditary class of graphs that admits such an algorithm while not being $\chi$-bounded.

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.

Desk Editor's Note private letter to a colleague

Burling graphs now have poly-time recognition via strict frame representations, yielding poly-time MIS and marking the first non-χ-bounded hereditary class with that feature.

read the letter

The main thing here is that the paper supplies a polynomial-time algorithm to recognize Burling graphs by building a strict frame representation, then uses the representation to solve maximum independent set in polynomial time. This makes Burling graphs the first hereditary class known to have efficient MIS while not being χ-bounded. The recognition step is the actual new piece; the MIS algorithm follows once the representation is in hand, and the paper states the χ-boundedness consequence directly. The work fills a specific gap because Burling graphs were already known from the triangle-free high-chromatic construction, but no prior algorithm handled recognition or MIS for the class. The logical chain in the abstract and stress-test note holds without visible circularity or unsupported reductions. The soft spots are small and expected for an abstract-level view. The full proof details for the polynomial-time construction are not visible here, so the exact running-time analysis would need checking, but nothing in the given material suggests a hidden exponential subroutine or a load-bearing assumption that fails. The result stays narrow, applying only to this one class. This paper is for people working on hereditary graph classes, the boundary between χ-boundedness and algorithmic tractability, and independent-set algorithms. It deserves a serious referee because it supplies a concrete, falsifiable separation between those properties. I would send it to peer review.

Referee Report

2 major / 0 minor

Summary. The paper claims to provide a polynomial-time algorithm to decide whether a given graph is a Burling graph and, if so, to construct its strict frame representation; this representation then yields a polynomial-time algorithm for the maximum independent set problem on Burling graphs. As a consequence, Burling graphs are presented as the first known hereditary class admitting polynomial-time MIS while not being χ-bounded.

Significance. If the claimed algorithms and their correctness proofs hold, the result would be significant: it supplies the first concrete hereditary class separating polynomial-time MIS from χ-boundedness, sharpening the boundary between structural and algorithmic properties of hereditary classes.

major comments (2)

[Abstract] Abstract: the manuscript supplies no description of the recognition algorithm, no proof outline, no running-time analysis, and no correctness argument, so the support for the central claim of polynomial-time recognition via strict frame construction cannot be assessed.
[Abstract] Abstract: the claim that the representation 'directly enables' a polynomial-time MIS algorithm is stated without any indication of the reduction or subroutine used, leaving the logical chain from representation to MIS unverified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their report. The two major comments concern the level of detail provided in the abstract. The full manuscript contains the complete algorithms, proofs, running-time analyses, and correctness arguments, but we agree the abstract can be strengthened to better outline these elements and will revise it accordingly.

read point-by-point responses

Referee: [Abstract] Abstract: the manuscript supplies no description of the recognition algorithm, no proof outline, no running-time analysis, and no correctness argument, so the support for the central claim of polynomial-time recognition via strict frame construction cannot be assessed.

Authors: We agree that the abstract, as a concise summary, omits detailed descriptions of the recognition algorithm, proof outlines, running-time analysis, and correctness arguments. These elements are fully developed in the body of the manuscript. To address the concern, we will revise the abstract to include a brief outline of the recognition procedure via strict frame construction, its polynomial running time, and a high-level correctness sketch. revision: yes
Referee: [Abstract] Abstract: the claim that the representation 'directly enables' a polynomial-time MIS algorithm is stated without any indication of the reduction or subroutine used, leaving the logical chain from representation to MIS unverified.

Authors: The abstract employs 'directly enables' to signal the logical consequence of the representation for the MIS problem. The manuscript details the specific reduction and dynamic-programming subroutine on the strict frame representation that yields the polynomial-time MIS algorithm. We will revise the abstract to briefly indicate this subroutine, thereby clarifying the chain from representation to MIS. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines Burling graphs equivalently via induced subgraphs of Burling's construction or via admitting a strict frame representation, then claims independent polynomial-time algorithms for recognition (by constructing the representation) and for maximum independent set (using the representation). No step reduces by construction to fitted inputs, self-citations, or renamed known results; the recognition-to-representation-to-MIS chain is presented as a self-contained algorithmic contribution without load-bearing self-referential elements or ansatzes smuggled via citation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are extractable from the provided text.

pith-pipeline@v0.9.0 · 5631 in / 1003 out tokens · 27156 ms · 2026-05-23T22:54:11.800524+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

On a coloring problem.Mathematica Scandinavica, 8:181–188, 1960

Edgar Asplund and Branko Grünbaum. On a coloring problem.Mathematica Scandinavica, 8:181–188, 1960

work page 1960
[2]

Burling.On coloring problems of families of polytopes

James P. Burling.On coloring problems of families of polytopes . PhD thesis, University of Colorado, Boulder, 1965

work page 1965
[3]

Restricted frame graphs and a conjecture of Scott.The Electronic Journal of Combinatorics , 23(1):Article P1.30, 2016

Jérémie Chalopin, Louis Esperet, Zhentao Li, and Patrice Ossona de Mendez. Restricted frame graphs and a conjecture of Scott.The Electronic Journal of Combinatorics , 23(1):Article P1.30, 2016

work page 2016
[4]

Triangle-free graphs with large chromatic number and no induced wheel.Journal of Graph Theory, 103(1):112–118, 2023

James Davies. Triangle-free graphs with large chromatic number and no induced wheel.Journal of Graph Theory, 103(1):112–118, 2023

work page 2023
[5]

Some polynomial algorithms for certain graphs and hypergraphs

András Frank. Some polynomial algorithms for certain graphs and hypergraphs. In Crispin Nash-Williams and John Sheehan, editors,Proceedings of the Fifth British Combinatorial Conference , volume XV ofCongressus Numerantium, pages 211–226. Utilitas Mathematica, 1976

work page 1976
[6]

Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973

Fănică Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973

work page 1973
[7]

Maximum weight independent sets and cliques in intersection graphs of filaments.Information Processing Letters, 73(5–6):181–188, 2000

Fănică Gavril. Maximum weight independent sets and cliques in intersection graphs of filaments.Information Processing Letters, 73(5–6):181–188, 2000

work page 2000
[8]

Coloring triangle-free rectangle overlap graphs with O(log logn) colors

Tomasz Krawczyk, Arkadiusz Pawlik, and Bartosz Walczak. Coloring triangle-free rectangle overlap graphs with O(log logn) colors. Discrete and Computational Geometry , 53(1):199–220, 2015

work page 2015
[9]

On-line approach to off-line coloring problems on graphs with geometric representations

Tomasz Krawczyk and Bartosz Walczak. On-line approach to off-line coloring problems on graphs with geometric representations. Combinatorica, 37(6):1139–1179, 2017

work page 2017
[10]

Trotter, and Bartosz Walczak

Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free geometric intersection graphs with large chromatic number.Discrete and Computational Geometry, 50(3):714–726, 2013

work page 2013
[11]

Trotter, and Bartosz Walczak

Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number.Journal of Combinatorial Theory, Series B , 105:6–10, 2014

work page 2014
[12]

Burling graphs revisited, part I: New characterizations.European Journal of Combinatorics , 110:Article 103686, 2023

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part I: New characterizations.European Journal of Combinatorics , 110:Article 103686, 2023

work page 2023
[13]

Burling graphs revisited, part II: Structure.European Journal of Combinatorics, 116:Article 103849, 2024

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part II: Structure.European Journal of Combinatorics, 116:Article 103849, 2024

work page 2024
[14]

Burling graphs revisited, part III: Applications toχ-boundedness

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part III: Applications toχ-boundedness. European Journal of Combinatorics , 116:Article 103850, 2024

work page 2024
[15]

Alex D. Scott. Induced trees in graphs of large chromatic number.Journal of Graph Theory , 24(4):297–311, 1997

work page 1997
[16]

A polynomial Turing-kernel for weighted independent set in bull-free graphs.Algorithmica, 77(3):619–641, 2017

Stéphan Thomassé, Nicolas Trotignon, and Kristina Vušković. A polynomial Turing-kernel for weighted independent set in bull-free graphs.Algorithmica, 77(3):619–641, 2017. (Paweł Rzążewski) Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland, and Institute of Informatics, University of Warsaw, Warsaw, Poland Emai...

work page 2017

[1] [1]

On a coloring problem.Mathematica Scandinavica, 8:181–188, 1960

Edgar Asplund and Branko Grünbaum. On a coloring problem.Mathematica Scandinavica, 8:181–188, 1960

work page 1960

[2] [2]

Burling.On coloring problems of families of polytopes

James P. Burling.On coloring problems of families of polytopes . PhD thesis, University of Colorado, Boulder, 1965

work page 1965

[3] [3]

Restricted frame graphs and a conjecture of Scott.The Electronic Journal of Combinatorics , 23(1):Article P1.30, 2016

Jérémie Chalopin, Louis Esperet, Zhentao Li, and Patrice Ossona de Mendez. Restricted frame graphs and a conjecture of Scott.The Electronic Journal of Combinatorics , 23(1):Article P1.30, 2016

work page 2016

[4] [4]

Triangle-free graphs with large chromatic number and no induced wheel.Journal of Graph Theory, 103(1):112–118, 2023

James Davies. Triangle-free graphs with large chromatic number and no induced wheel.Journal of Graph Theory, 103(1):112–118, 2023

work page 2023

[5] [5]

Some polynomial algorithms for certain graphs and hypergraphs

András Frank. Some polynomial algorithms for certain graphs and hypergraphs. In Crispin Nash-Williams and John Sheehan, editors,Proceedings of the Fifth British Combinatorial Conference , volume XV ofCongressus Numerantium, pages 211–226. Utilitas Mathematica, 1976

work page 1976

[6] [6]

Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973

Fănică Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973

work page 1973

[7] [7]

Maximum weight independent sets and cliques in intersection graphs of filaments.Information Processing Letters, 73(5–6):181–188, 2000

Fănică Gavril. Maximum weight independent sets and cliques in intersection graphs of filaments.Information Processing Letters, 73(5–6):181–188, 2000

work page 2000

[8] [8]

Coloring triangle-free rectangle overlap graphs with O(log logn) colors

Tomasz Krawczyk, Arkadiusz Pawlik, and Bartosz Walczak. Coloring triangle-free rectangle overlap graphs with O(log logn) colors. Discrete and Computational Geometry , 53(1):199–220, 2015

work page 2015

[9] [9]

On-line approach to off-line coloring problems on graphs with geometric representations

Tomasz Krawczyk and Bartosz Walczak. On-line approach to off-line coloring problems on graphs with geometric representations. Combinatorica, 37(6):1139–1179, 2017

work page 2017

[10] [10]

Trotter, and Bartosz Walczak

Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free geometric intersection graphs with large chromatic number.Discrete and Computational Geometry, 50(3):714–726, 2013

work page 2013

[11] [11]

Trotter, and Bartosz Walczak

Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number.Journal of Combinatorial Theory, Series B , 105:6–10, 2014

work page 2014

[12] [12]

Burling graphs revisited, part I: New characterizations.European Journal of Combinatorics , 110:Article 103686, 2023

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part I: New characterizations.European Journal of Combinatorics , 110:Article 103686, 2023

work page 2023

[13] [13]

Burling graphs revisited, part II: Structure.European Journal of Combinatorics, 116:Article 103849, 2024

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part II: Structure.European Journal of Combinatorics, 116:Article 103849, 2024

work page 2024

[14] [14]

Burling graphs revisited, part III: Applications toχ-boundedness

Pegah Pournajafi and Nicolas Trotignon. Burling graphs revisited, part III: Applications toχ-boundedness. European Journal of Combinatorics , 116:Article 103850, 2024

work page 2024

[15] [15]

Alex D. Scott. Induced trees in graphs of large chromatic number.Journal of Graph Theory , 24(4):297–311, 1997

work page 1997

[16] [16]

A polynomial Turing-kernel for weighted independent set in bull-free graphs.Algorithmica, 77(3):619–641, 2017

Stéphan Thomassé, Nicolas Trotignon, and Kristina Vušković. A polynomial Turing-kernel for weighted independent set in bull-free graphs.Algorithmica, 77(3):619–641, 2017. (Paweł Rzążewski) Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland, and Institute of Informatics, University of Warsaw, Warsaw, Poland Emai...

work page 2017