zbMATH — the first resource for mathematics

Necessary edges in \(k\)-chordalisations of graphs. (English) Zbl 1031.05120
Summary: A \(k\)-chordalisation of a graph \(G = (V,E)\) is a graph \(H = (V,F)\) obtained by adding edges to \(G\), such that \(H\) is a chordal graph with maximum clique size at most \(k\). This note considers the problem: given a graph \(G = (V,E)\) which pairs of vertices, non-adjacent in \(G\), will be an edge in every \(k\)-chordalisation of \(G\)? Such a pair is called necessary for treewidth \(k\). An equivalent formulation is: which edges can one add to a graph \(G\) such that every tree decomposition of \(G\) of width at most \(k\) is also a tree decomposition of the resulting graph \(G'\)? Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth \(k\). For a fixed \(k\), one can find in linear time for a given graph \(G\) the set of all necessary pairs for treewidth \(k\). If \(k\) is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI