E-resources
Peer reviewed
Open access
-
Janzer, Barnabás; Janzer, Oliver
Journal of combinatorial theory. Series B, November 2024, 2024-11-00, Volume: 169Journal Article
Given a graph H, let g(n,H) denote the smallest k for which the following holds. We can assign a k-colouring fv of the edge set of Kn to each vertex v in Kn with the property that for any copy T of H in Kn, there is some u∈V(T) such that every edge in T has a different colour in fu. The study of this function was initiated by Alon and Ben-Eliezer. They characterized the family of graphs H for which g(n,H) is bounded and asked whether it is true that for every other graph g(n,H) is polynomial. We show that this is not the case and characterize the family of connected graphs H for which g(n,H) grows polynomially. Answering another question of theirs, we also prove that for every ε>0, there is some r=r(ε) such that g(n,Kr)≥n1−ε for all sufficiently large n. Finally, we show that the above problem is connected to the Erdős–Gyárfás function in Ramsey Theory, and prove a family of special cases of a conjecture of Conlon, Fox, Lee and Sudakov by showing that for each fixed r the complete r-uniform hypergraph Kn(r) can be edge-coloured using a subpolynomial number of colours in such a way that at least r colours appear among any r+1 vertices.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
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.