E-resources
Peer reviewed
Open access
-
Fernández, Irene Gil; Hyde, Joseph; Liu, Hong; Pikhurko, Oleg; Wu, Zhuo
Journal of combinatorial theory. Series B, July 2023, 2023-07-00, Volume: 161Journal Article
A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that there is a constant C such that every graph with average degree at least Ck2 has a subdivision of Kk, the complete graph on k vertices. We study two directions extending this result.•Verstraëte conjectured that a quadratic bound guarantees in fact two vertex-disjoint isomorphic copies of a Kk-subdivision.•Thomassen conjectured that for each k∈N there is some d=d(k) such that every graph with average degree at least d contains a balanced subdivision of Kk. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d(k) remains open. In this paper, we show that a quadratic lower bound on average degree suffices to force a balanced Kk-subdivision. This gives the right order of magnitude of the optimal d(k) needed in Thomassen's conjecture. Since a balanced Kmk-subdivision trivially contains m vertex-disjoint isomorphic Kk-subdivisions, this also confirms Verstraëte's conjecture in a strong sense.
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.