×

Recognizing dual-chordal graphs. (English) Zbl 0993.05118

Summary: A dual-chordal graph is a 2-connected, 3-edge-connected graph \(G\) such that, for every cutset \(D\) that consists of at least four edges, removing \(D\) from \(G\) creates a bridge (cut-edge). Dual chordal graphs can be defended as being the correct cycle/cutset duals of chordal graphs (whether planar or not) and have several characterizations or varying similarity to characterizations of chordal graphs. A recognition algorithm involves repeatedly contracting three special kinds of subgraphs. Counting how many of each of these three kinds of subgraphs get contracted determines three parameters for dual-chordal graphs, and these parameters are associated with structural features of the graphs (including the crossing number and Crapo’s beta invariant).

MSC:

05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite