Polynomial-time recognition and maximum independent set in Burling graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915956415004672 |
|---|---|
| author | Rzążewski, Paweł Walczak, Bartosz |
| author_facet | Rzążewski, Paweł Walczak, Bartosz |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16666 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial-time recognition and maximum independent set in Burling graphs Rzążewski, Paweł Walczak, Bartosz Combinatorics Discrete Mathematics 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. |
| title | Polynomial-time recognition and maximum independent set in Burling graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2407.16666 |