Quasicolorable coloring of a graph
Source: HMIC 2022/4
April 8, 2022
graph theorycombinatorics
Problem Statement
Call a simple graph quasicolorable if we can color each edge blue, red, green, or white such that[*] for each vertex v of degree 3 in G, the three edges incident to v are either (1) red,
green, and blue, or (2) all white,
[*] not all edges are white.A simple connected graph has vertices of degree , vertices of degree , and no other vertices, where and are positive integers. Find the smallest real number so that the following statement is true: “If , then must be quasicolorable.”