Pith. sign in

REVIEW 1 cited by

Excluding a clique or a biclique in graphs of bounded induced matching treewidth

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2405.04617 v2 pith:R35GXEPE submitted 2024-05-07 math.CO

classification math.CO
keywords boundedinducedmatchingtreewidthgraphsmathcalnumberbiclique
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

For a tree decomposition $\mathcal{T}$ of a graph $G$, let $\mu(\mathcal{T})$ denote the maximum size of an induced matching in $G$ with the property that some bag of $\mathcal{T}$ contains at least one endpoint of every edge of the matching. The induced matching treewidth of a graph $G$ is the minimum value of $\mu(\mathcal{T})$ over all tree decompositions $\mathcal{T}$ of $G$. Classes of graphs with bounded induced matching treewidth admit polynomial-time algorithms for a number of problems, including INDEPENDENT SET, $k$-COLORING, ODD CYCLE TRANSVERSAL, and FEEDBACK VERTEX SET. In this paper, we focus on combinatorial properties of such classes. First, we show that graphs with bounded induced matching treewidth that exclude a fixed biclique as an induced subgraph have bounded tree-independence number, which is another well-studied parameter defined in terms of tree decompositions. This sufficient condition about excluding a biclique is also necessary, as bicliques have unbounded tree-independence number. Second, we show that graphs with bounded induced matching treewidth that exclude a fixed clique have bounded chromatic number, that is, classes of graphs with bounded induced matching treewidth are $\chi$-bounded. The two results confirm two conjectures due to Lima et al. [ESA 2024].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Induced subgraphs of graphs with large deficiency

    math.CO 2025-05 conditional novelty 6.0 of 10

    Connected graphs with bounded local independence and only admitted odd or even bones have matching deficiency at most explicit extremal formulas.

Pith tools