Cover and variable degeneracy (Q2075519)

Classically we say a graph \(G\) is \(k\)-degenerate if and only if every subgraph of \(G\) has a vertex which has degree at most \(k\) in that subgraph. Similarly it is strictly \(k\)-degenerate if every subgraph has a vertex of degree strictly less than \(k\), which is sometimes what is really wanted. Degenerate graphs often crop up in colouring problems where degeneracy makes various e.g. inductive arguments work: for example the coloring number of a graph is the smallest \(k\) such that \(G\) is strictly \(j\)-degenerate, it is often a better upper bound on chromatic number than e.g. Brooks' theorem gives. In the article under review, the authors study a generalisation introduced in [\textit{O. V. Borodin} et al., ibid. 214, No. 1--3, 101--112 (2000; Zbl 0949.05029)]. Given a function \(f: V(G)\rightarrow \mathbb{N}\), we say \(G\) is strictly \(f\)-degenerate if every subgraph \(\Gamma\) has a vertex \(v\) whose degree in \(\Gamma\) is strictly less than \(f(v)\). The main focus in the paper under review is on a link with transversals. Recall that a cover \(H\) of a graph \(G\) is a graph whose vertex set is \(\cup_{v\in V(G)}X_{v}\) where the \(X_{v}\) are disjoint \(s\)-element sets (thought of as the vertices above each vertex of \(G\)) for some fixed \(s\), with the edge set of \(H\) being the union of the edge sets between \(X_{u}\) and \(X_{v}\) for each \(uv\in E(G)\), each such edge set being a matching. A transversal of \(H\) is a set \(R\subseteq V(H)\) such that \(\vert R\cap X_{v}\vert =1\) for every \(v\in V(G)\). We now say a transversal \(R\) is a strictly \(f\)-degenerate transversal if the subgraph of \(H\) induced by \(R\) is strictly \(f\)-degenerate. The authors show that strictly \(f\)-degenerate transversals generalise various notions in graph colouring. They give a result which is a generalisation in their context of Brooks' theorem in usual graph colouring or choosability. They give a result generalising Gallai's result that in a \((k+1)\)critical graph the vertices of degree \(k\) induce a graph in which every block is a complete graph or odd cycle. They use their results to reprove some known results and also some new results in graph colouring, for example that every graph with no \(K_{4}\)-minor can be partitioned into an independent set and an induced forest.