Polynomial-time recognition and maximum independent set in Burling graphs
For graph theorists and algorithm designers, this solves open problems about recognition and optimization in a class of triangle-free high-chromatic graphs.
The paper provides polynomial-time algorithms for recognizing Burling graphs and solving the maximum independent set problem on them, establishing them as the first hereditary graph class with such algorithms that is not χ-bounded.
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 $χ$-bounded.