MathDB
edge and endpoints same color

Source: miklos schweitzer 1997 q1

September 20, 2021
graph theory

Problem Statement

Define a class of graphs GkG_k for each positive integer k as follows. A graph G = ( V , E ) is an element of GkG_k if and only if there exists an edge coloring ψ:E→[k]={1,2,...,k}\psi: E\to [ k ] = \{1,2, ..., k\} such that for all vertex coloring ϕ:V→[k]\phi: V\to [ k ] there exist an edge e = { x , y } such that ϕ(x)=ϕ(y)=ψ(e)\phi ( x ) = \phi( y ) = \psi( e ). Prove that there exist c1<c2c_1< c_2 positive constants with the following two properties: (i) each graph in GkG_k has at least c1k2c_1 k^2 vertices; (ii) there is a graph in GkG_k which has at most c2k2c_2 k^2 vertices.
Back to ProblemsView on AoPS