Polynomial-time recognition and maximum independent set in Burling graphs
<|reference_start|>Polynomial-time recognition and maximum independent set in Burling graphs: A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. We provide a polynomial-time algorithm which decides whether a given graph is a Burling graph and if it is, constructs its intersection model by rectangular frames. That model 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.<|reference_end|>
@article{rzążewski2024polynomial-time,
    title={Polynomial-time recognition and maximum independent set in Burling
  graphs},
    author={Pawe{l} Rzk{a}.zewski, Bartosz Walczak},
    journal={arXiv preprint arXiv:2407.16666},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.16666},
    primaryClass={math.CO cs.DM}
}