# 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.

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