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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Polynomial-Time Recognition and Maximum Independent Set in Burling Graphs

  • Paweł Rzążewski,
  • Bartosz Walczak

摘要

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.