Two remarks on the coloring number (Q1362106): Difference between revisions

Let \(G\) be a graph. Its coloring number, \(\text{Col}(G)\), denotes the least cardinal \(\kappa\) such that there exists a well-ordering of the vertices with the property that each vertex is joined to less than \(\kappa\) smaller vertices. The author shows the following two results: (1) If \(k\) is finite and \(G\) is a graph with \(\text{Col}(G)= k+1\), then there exists a subgraph \(H\subseteq G\) with \(\text{Col}(H)= k\). (2) If \(G\) is an infinite graph of cardinality \(\lambda\) with \(\text{Col}(G)=\kappa\) and \(<\) is an arbitrary well-ordering of the vertices, then there are \(\lambda\) points with only less than \(\kappa\) edges going down.