MathDB
Problems
Contests
Undergraduate contests
Miklós Schweitzer
1997 Miklós Schweitzer
1
1
Part of
1997 Miklós Schweitzer
Problems
(1)
edge and endpoints same color
Source: miklos schweitzer 1997 q1
9/20/2021
Define a class of graphs
G
k
G_k
G
k
for each positive integer k as follows. A graph G = ( V , E ) is an element of
G
k
G_k
G
k
if and only if there exists an edge coloring
ψ
:
E
→
[
k
]
=
{
1
,
2
,
.
.
.
,
k
}
\psi: E\to [ k ] = \{1,2, ..., k\}
ψ
:
E
→
[
k
]
=
{
1
,
2
,
...
,
k
}
such that for all vertex coloring
ϕ
:
V
→
[
k
]
\phi: V\to [ k ]
ϕ
:
V
→
[
k
]
there exist an edge e = { x , y } such that
ϕ
(
x
)
=
ϕ
(
y
)
=
ψ
(
e
)
\phi ( x ) = \phi( y ) = \psi( e )
ϕ
(
x
)
=
ϕ
(
y
)
=
ψ
(
e
)
. Prove that there exist
c
1
<
c
2
c_1< c_2
c
1
<
c
2
positive constants with the following two properties: (i) each graph in
G
k
G_k
G
k
has at least
c
1
k
2
c_1 k^2
c
1
k
2
vertices; (ii) there is a graph in
G
k
G_k
G
k
which has at most
c
2
k
2
c_2 k^2
c
2
k
2
vertices.
graph theory