It is known that each vertex of the convex polyhedron $P$ belongs to three different faces, and each vertex of $P$ can be dyed black and white, so that the two endpoints of each edge of $P$ are different colors. Proof: The interior of each edge of $P$ can be dyed red, yellow, and blue, so that the colors of the three edges connected to each vertex are different, and each face contains two colors of edges. Created by Liang Xiao
Problem
Source: 2024 CTST P1
Tags: combinatorics, colouring, 2024 CTST, China TST
06.03.2024 09:11
Not too hard, took 20 minutes just now. It is well known that the polyhedron can be represented as a planar graph. The condition of $2$-colorability of the vertices translates to its bipartiteness. Also, since each vertex is in three faces, it has degree $3$. We claim that the faces of this planar graph can be $3$-colored. Then, for any edge $e$, if the two faces it is in are $A$ and $B$, simply color the edge $e$ with the third color. This will allow each face to contain two colors, and for any vertex $v$, if the three faces it is in have colors $A$, $B$, $C$ (all distinct), then the edges will also be $A$, $B$, $C$, thus satisfying the problem condition. Note that as the graph is bipartite, the number of edges on each face must be even. Thus, this reduces to a famous theorem: Steinberg 1993 wrote: Any cubic map where each region has an even number of neighbors can be colored using 3 colors. Comments: It is quite easy to note that the graph is bipartite, has degree $3$. Then, the idea of coloring the faces is not too hard to think of, and actually forced. If you know this theorem, then it is extremely easy.
08.03.2024 07:25
A related problem, also from China, 30 years ago, seems like it was nearly the same: (1991 China MO P6) A football is covered by some polygonal pieces of leather which are sewed up by three different colors threads. It features as follows: any edge of a polygonal piece of leather is sewed up with an equal-length edge of another polygonal piece of leather by a certain color thread; each node on the ball is vertex to exactly three polygons, and the three threads joint at the node are of different colors. Show that we can assign to each node on the ball a complex number (not equal to $1$), such that the product of the numbers assigned to the vertices of any polygonal face is equal to $1$.
19.03.2024 06:07
Sketch of result cited above: Consider the dual question with regions represented as vertices and neighboring faces represented by edges. Then it is well known that we can place this figure in the plane so that none of it's edges intersect. Now we need to show that a triangulation of a plane figure with even degree has a chromatic edge coloring number of $3$. This follows by induction by repeatedly removing the set of outward-most edges along the boundary. Algorithm (Not Proof): Consider such a black-white assignment guaranteed by the statement. Choose an arbitrary node, if the node is black color the adjacent edges red, yellow, and blue in a clockwise order, if the node is white color the adjacent edges red, yellow, and blue in a counter-clockwise order. Next choose a vertex with one of it's edges already colored and then color its other two edges to match the orientation corresponding to the color of the vertex. Now repeat this process until all of the edges are colored.
29.03.2024 17:25
the problem can be done by assigning roots of unity , i think
28.05.2024 10:03
We take the obvious planar graph representation. The transformed problem is as follows: A bipartite planar graph is given such that each vertex has degree $3$. Show that the regions defined by the edges of the graph (including the infinite region "outside" the graph) can be colored in three colors such that no two regions of the same color share an edge. Here we give a construction for the coloring. Color the vertices black and white in the bipartite fashion, then replace each edge with a directed edge pointing from the white vertex to the black vertex. Define the score $S$ of a path from region $A$ to region $B$ (i.e. a sequence of regions starting with $A$ and ending with $B$ where consecutive regions are connected via a common edge) to be the number of left-facing edges crossed minus the number of right-facing edges crossed during the path. We claim that the score of any path from $A$ to $B$, when taken mod $3$, depends on the choice of $A$ and $B$ only (and not the choice of the path itself). It suffices to show that any "loop" from $A$ to $A$ has score $S \equiv 0 \pmod 3$. To prove this, for convenience suppose that this loop does not intersect itself (otherwise we can split it into two smaller loops) and that the loop goes counterclockwise. Considering the vertices inside the area $T$ enclosed by the loop, by counting the indegrees and outdegrees we easily obtain \[ S = 3(\text{\# black vertices in $T$} - \text{\# white vertices in $T$}) \]which is a multiple of $3$, hence proved. Now to obtain the actual coloring, simply pick an arbitrary region $P$ and color every region $R$ based on the mod-$3$ score from $P$ to $R$ - then no two neighbouring regions will have the same color since they are separated by just one edge, so their scores will have a difference of $\pm 1 \pmod 3$.
03.06.2024 07:13
Is it possible to induct with dual graph stuff? The hypothesis for the induction would be that for any plane graph with a nondegenerate polygon as the unbounded face, all other faces being triangles, and all interior vertices having even degree, there exists a valid coloring of the edges with the stronger condition that two adjacent edges of the unbounded face have the same color iff the vertex has odd degree. Removal of vertex for the induction would be valid because it's impossible for every vertex of the unbounded face to be connected to at least three vertices of the unbounded face.