A note on generalized chromatic number and generalized girth (Q1970697): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| (One intermediate revision by one other user not shown) | |||
| Property / arXiv ID | |||
| Property / arXiv ID: math/9807044 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2044469686 / rank | |||
Normal rank | |||
Latest revision as of 10:04, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on generalized chromatic number and generalized girth |
scientific article |
Statements
A note on generalized chromatic number and generalized girth (English)
0 references
21 March 2000
0 references
\textit{P. Erdős} [Graph theory and probability, Can. J. Math. 11, 34-38 (1959; Zbl 0084.39602)] proved that there are graphs with arbitrarily large girth and chromatic number. The paper under review proves a similar result for a generalized chromatic number and generalized girth. For a given graph \(H\), the \(H\)-chromatic number of \(G\) is the minimum size of a partition of \(V(G)\) into classes that induce subgraphs of \(G\) not containing \(H\) as a subgraph, the \(H\)-girth of \(G\) is somewhat more complicated.
0 references
forbidden subgraph
0 references
girth
0 references
chromatic number
0 references
