Two remarks on the coloring number (Q1362106): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q587432 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Martin Weese / rank | |||
Normal rank |
Revision as of 09:16, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two remarks on the coloring number |
scientific article |
Statements
Two remarks on the coloring number (English)
0 references
12 August 1997
0 references
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.
0 references
chromatic number
0 references
coloring number
0 references
well-ordering
0 references