UP - logo
University of Primorska University Library - all departments (UPUK)
  • Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
    Bonamy, Marthe ...
    A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial ... time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. (The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594)
    Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 167, jul. 2024, str. 215-249)
    Type of material - article, component part ; adult, serious
    Publish date - 2024
    Language - english
    COBISS.SI-ID - 192772867

    Link(s):

    https://www.sciencedirect.com/science/article/pii/S0095895624000212?via%3Dihub
    https://doi.org/10.1016/j.jctb.2024.03.003
    DOI

source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 167, jul. 2024, str. 215-249)

loading ...
loading ...
loading ...

Shelf entry