A note on the interval number of a graph (Q1065014): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q106026156, #quickstatements; #temporary_batch_1707232231678 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q106026156 / rank | |||
Normal rank |
Revision as of 17:37, 6 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the interval number of a graph |
scientific article |
Statements
A note on the interval number of a graph (English)
0 references
1985
0 references
Three results on the interval number \(i(G)\) and d-dimensional interval number \(i_d(G)\) of a graph \(G\) with n vertices are presented. Theorem 1. The inequalities \(i(G)\geq n/4 lg_2 n\), \(i_d(G)\geq n/4d lg_2 n\) hold for almost every graph (i.e. the probability, that the lower bounds hold, goes to 1 as \(n\to \infty\) in the probability spaces containing all graphs on \(n\) vertices, each of them with the same probability). The first lower bound is also asymptotically true for almost every bipartite graph. Theorem 2. There exist \(K_{m,n}\)-free bipartite graphs with interval number at least \(c(m)\cdot n^{1-2(m+1)}/lg_2 n\), which can be improved to \(\sqrt{n}/4+o(\sqrt{n})\) for \(m=2\) and \((n/2)^{2/3}/lg_2 n\) for \(m=3\). Theorem 3. There exist regular graphs of girth at least \(g\) with interval number at least \(((n-1)/2)^{1/(g-2)}\).
0 references
interval number
0 references
almost every graph
0 references
lower bounds
0 references
bipartite graphs
0 references
regular graphs
0 references