On the maximum cardinality search lower bound for treewidth Original Research Article

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex image in an MCS-ordering is the number of neighbours of image that are before image in the ordering. The visited degree of an MCS-ordering image of image is the maximum visited degree over all vertices image in image. The maximum visited degree over all MCS-orderings of graph image is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345–353] showed that the treewidth of a graph image is at least its maximum visited degree.