Two remarks on the coloring number (Q1362106): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5808059 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On chromatic number of graphs and set-systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871790 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinct representatives of subsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Representatives of Subsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Colouring Number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a conjecture of Rödl and Voigt / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A compactness theorem for singular cardinals, free algebras, Whitehead problem and transversals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On incompactness for chromatic number of graphs / rank | |||
Normal rank |
Latest revision as of 17:53, 27 May 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
0 references