Precoloring 3-extension on outerplanar graphs

This paper proves that for connected outerplanar graphs containing at most one or two triangles, any precoloring of two or three non-adjacent vertices can be extended to a proper 3-coloring of the entire graph.

The Gist

Here is an explanation of the paper "A note on the precoloring extension of outerplane graphs," translated into simple language with creative analogies.

The Big Picture: The "Coloring Party" Problem

Imagine you have a map of a city (a graph) drawn on a flat piece of paper. The intersections are vertices (dots), and the roads are edges (lines).

The rule of the game is 3-Coloring: You have three paint buckets (Red, Blue, Green). You must paint every intersection so that no two intersections connected by a road have the same color.

Usually, this is easy. But sometimes, the city planners (the mathematicians) come in before you start painting and say, "Hey, we've already painted these specific intersections. You must keep those colors." This is called Precoloring Extension. The question is: Can you finish the rest of the map without breaking the rules, given these pre-painted spots?

The Setting: "Outerplanar" Cities

The paper focuses on a specific type of city layout called an outerplanar graph.

• Analogy: Imagine a neighborhood where every house is built right on the edge of a giant, circular park. There are no houses "inside" the park surrounded by other houses. Everyone is on the "outer face."
• The Constraint: These cities can have a few "triangles" (three houses all connected to each other, like a tiny triangular block). The paper asks: How many pre-painted houses can we have before the whole coloring job becomes impossible?

The Main Discovery: The "Diamond" Trap

The authors found that for these outerplanar cities, you can almost always finish the job if you pre-paint three independent houses (if there is only one triangle in the city) or two independent houses (if there are two triangles).

However, there is a catch: The "Diamond."

• The Diamond Analogy: Imagine two triangles sharing a common wall. It looks like a diamond shape (two triangles stuck together).
• The Problem: If you pre-paint the two "pointy" tips of this diamond, they must be the same color. If the planners paint them different colors, the whole neighborhood becomes impossible to color.
• The Solution: The paper proves that as long as the pre-painted houses follow the rules of the Diamond (or don't form a Diamond at all), you can always finish the painting job.

How They Proved It: The "Magic Mirror" (Homomorphism)

Mathematicians don't just guess; they build proofs. The authors used a clever tool called Homomorphism.

• The Analogy: Imagine you have a complex, messy room (the big graph) and a tiny, simple toy box (a triangle with 3 colors).
• The Magic: The authors showed that you can "squash" the messy room into the toy box. If you can map the messy room onto the toy box without breaking the rules, then the messy room can definitely be colored with 3 colors.
• The Algorithm: They created a step-by-step recipe (an algorithm) to adjust the colors. If a section of the map gets stuck, the algorithm says, "Okay, let's swap the colors in this specific neighborhood using a pre-approved pattern," and suddenly, the whole map fits together perfectly.

The "Cake" and "Hamburger" Structures

To handle the tricky cases where there are two triangles, the authors invented funny names for specific shapes they found:

1. The Cake: Two triangles sitting next to each other, sharing a corner, looking like layers of a cake.
2. The Hamburger: A triangle sitting next to a square or pentagon, looking like a burger bun.

They proved that if your city looks like a Cake or a Hamburger, you can still finish the coloring job, provided you follow their specific color-swapping rules.

Summary of the Results

1. One Triangle City: You can pre-paint any 3 houses (as long as they aren't touching), and you can always finish the job.
2. Two Triangle City: You can pre-paint any 2 houses, unless they form a "Diamond" and are painted different colors. If they are the "Diamond points," they must be the same color.
3. The Method: They used a "color-shifting algorithm" (like a magic mirror) to prove that no matter how the houses are arranged, you can always find a way to make the colors work.

Why Does This Matter?

This is like solving a puzzle that helps computer scientists and network engineers understand how to assign resources (like frequencies for cell towers or time slots for meetings) without conflicts. By understanding the limits of these "outerplanar" shapes, we know exactly how much flexibility we have before a system breaks.

In short: The paper says, "Don't worry about the pre-painted houses! As long as you respect the 'Diamond' rule, we have a magic recipe to color the whole map."

Technical Summary

Here is a detailed technical summary of the paper "A note on the precoloring extension of outerplane graphs" by Xingchao Deng, Beiyan Zou, and Hong Zhai.

1. Problem Statement

The paper addresses the Precoloring Extension Problem within the context of outerplanar graphs (graphs that can be embedded in the plane such that all vertices lie on the boundary of the outer face).

• Core Question: Given a graph $G$ and a partial coloring (precoloring) of a subset of vertices $W \subseteq V(G)$, can this partial coloring be extended to a proper $k$-coloring of the entire graph?
• Specific Focus: The authors investigate 3-colorability for outerplanar graphs containing a limited number of triangles (specifically, at most one or two triangles).
• Context: This work builds upon Grötzsch's Theorem (triangle-free planar graphs are 3-colorable) and recent generalizations by La et al. [6] regarding planar graphs with at most one triangle. The authors specifically aim to resolve Problems 4.2 and 4.3 posed by La et al., which concern the extendability of precolorings for independent vertices in outerplanar graphs with triangular structures.

2. Methodology

The authors employ a combination of structural graph theory, graph homomorphisms, and algorithmic construction to prove their results.

• Structural Decomposition:

  • The paper analyzes biconnected outerplane graphs first, noting that 1-connected (connected) outerplane graphs are subgraphs of biconnected ones formed by edge additions.
  • Chord Addition: To simplify the analysis of faces, the authors add chords to the graph to decompose larger faces ($n \ge 6$) into 4-faces and 5-faces, ensuring all faces in the modified graph $H$ have length $\le 5$.
  • Triangle Classification: Triangles are categorized based on their position relative to the outer face boundary ($H$-embedding):
    • Marginal Triangle: Shares two edges with the outer boundary.
    • Striped Triangle: Shares one edge with the outer boundary.
    • Internal Triangle: Shares no edges with the outer boundary.
  • Diamond Structure ($D$): Defined as two triangles sharing a common edge. The authors identify that in a proper 3-coloring, the two non-adjacent "diamond vertices" (the tips of the diamond) must share the same color.

• Graph Homomorphisms:

  • The paper utilizes homomorphisms from faces (4-cycles and 5-cycles) to the complete graph $K_3$.
  • Specific mapping functions ($f_1$ through $f_6$ for 4-faces, and $F_1$ through $F_3$ for 5-faces) are defined to map face vertices to the colors $\{X, Y, Z\}$.
  • A priority order is established for these mappings to facilitate algorithmic adjustments.

• Algorithmic Approach:

  • Algorithm 1 (Color Adjusting Algorithm): A linear-time algorithm is proposed to adjust homomorphism mappings along a path of faces connecting two precolored independent vertices ($u$ and $v$).
  • The algorithm iteratively applies homomorphisms to faces. If a conflict arises (i.e., the target vertex $v$ cannot receive the desired color based on the current mapping of the preceding face), the algorithm switches to a lower-priority homomorphism for the previous face to resolve the conflict. This ensures that $u$ and $v$ can be assigned the same color if required.

• Proof Strategy:

  • The proofs for the main theorems are broken down into cases based on the number of triangles (one vs. two) and the specific configuration of the precolored vertices (all distinct colors, all same color, or mixed).
  • The authors often use a reduction technique: removing a vertex (often a degree-2 vertex in a marginal triangle) to reduce the graph to a case with fewer triangles, applying an inductive hypothesis or a known theorem (like Theorem 1.1 or 1.3), and then extending the coloring back.

3. Key Contributions and Results

The paper establishes two main theorems for biconnected outerplane graphs and extends them to 1-connected graphs via corollaries.

Theorem 1.5 (One Triangle Case)

• Result: In a biconnected outerplane graph containing at most one triangle, any precoloring of three independent vertices can be extended to a proper 3-coloring of the entire graph.
• Significance: This generalizes previous results by confirming that the presence of a single triangle does not obstruct the extension of precolorings for three independent vertices, regardless of whether the precolored vertices share colors or have distinct colors.

Theorem 1.6 (Two Triangles Case)

• Result: In a biconnected outerplane graph containing exactly two triangles, any precoloring of two independent vertices can be extended to a proper 3-coloring, provided one of the following conditions is met:
  1. The graph does not contain a "diamond" ($D$) subgraph.
  2. The graph contains a diamond, but the two precolored non-adjacent vertices share at most one vertex of the diamond.
  3. The graph contains a diamond, and the two precolored non-adjacent vertices are the "diamond vertices" (the tips of the diamond). In this specific case, they must be precolored with the same color.
• Significance: This theorem identifies the "diamond" structure as the critical obstruction. It proves that if the diamond structure exists, the precoloring is only extendable if the constraints imposed by the diamond (forcing the tips to share a color) are respected.

Corollaries 1.7 and 1.8

• The results are extended to 1-connected (connected) outerplane graphs containing one or two triangles, respectively, by noting that such graphs are subgraphs of biconnected outerplane graphs with the same triangle count.

4. Significance and Impact

• Resolution of Open Problems: The paper successfully addresses Problems 4.2 and 4.3 from La et al. [6], which were open questions regarding the precoloring extension of outerplanar graphs with triangular structures.
• Characterization of Obstructions: The work provides a precise characterization of when precoloring extension fails in outerplanar graphs. It highlights that the diamond structure is the primary structural barrier for 3-coloring extension when two triangles are present.
• Algorithmic Efficiency: By defining specific homomorphism mappings and a linear-time adjustment algorithm, the paper moves beyond existential proofs to provide a constructive method for finding the 3-coloring.
• Theoretical Advancement: The results deepen the understanding of the relationship between Grötzsch's Theorem and the extendability of colorings in graphs with limited triangular complexity, bridging the gap between planar and outerplanar graph theory.

5. Conclusion

The authors conclude that while the precoloring extension problem for outerplanar graphs with at most two triangles is largely solvable, the presence of a "diamond" subgraph imposes strict constraints on the precoloring of independent vertices. The paper effectively combines structural analysis with homomorphism-based algorithms to solve these specific instances, leaving the general case for graphs with more triangles (Problems 4.2, 4.3, and 4.4 in the general sense) as an area for future research.