A note on generalized chromatic number and generalized girth (Q1970697)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:1970697 |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.7952038049697876
0 references
0.7923347353935242
0 references
0.7876707315444946
0 references
0.787450909614563
0 references
0.787450909614563
0 references
