MathDB
Without induced paw

Source: Iran pre-preparation course examination 2011- P4

February 25, 2011
combinatorics proposedcombinatorics

Problem Statement

A star K1,3K_{1,3} is called a paw. suppose that GG is a graph without any induced paws. prove that χ(G)≤(ω(G))2\chi(G)\le(\omega(G))^2. (15 points)
Back to ProblemsView on AoPS