A note on the precoloring extension of outerplane graphs
Xingchao Deng, Beiyan Zou, Hong Zhai · 2026
Read A note on the precoloring extension of outerplane graphs by Xingchao Deng, Beiyan Zou, Hong Zhai (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05775.txt.
Introduction
Deng and team study pre-dyed vertices in linked outerplanar graphs holding at most one or two triangles. Earlier work showed that a pair of apart vertices plus a short face can always be finished to a three-color scheme in a related planar setting. The authors extend this picture by proving that any two or three apart pre-dyed vertices allow a full three-color scheme. Their result gives a clean stretching theorem for outerplanar graphs with few triangles.
Catalog record
| CREATOR | Xingchao Deng, Beiyan Zou, Hong Zhai |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36132 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05775
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the precoloring extension of outerplane graphs Thanks: c Corresponding author. [email protected] Xingchao Deng, Beiyan Zou, Hong Zhai Abstract The precoloring extension problem involves initially assigning colors to certain vertices and determining whether such a partial coloring can be extended to a proper k-coloring of the entire graph for an integer k k . In a landmark result, Grötzsch demonstrated that every planar graph without triangle is 3-colorable. A significant generalization of this theorem was recently achieved by La et al. [ 6 ] . In this paper, we establish that any precoloring of three independent vertices (or two independent vertices) can be extended to a 3-coloring of the entire graph when it is a connected outerplane graph containing at most one triangle (or two triangles, respectively). Keywords: Grötzsch’s Theorem; precoloring extension; homomorphism; 3-coloring; triangle AMS subject classification 2020: 05C10; 05C15; 05C75. 1 Introduction A graph G is termed a plane graph if it is embedded in the plane without edge crossings. A graph is planar if and only if it does not contain K_{5} or K_{3,3} minor, according to Kuratowski’s theorem. A Hamilton cycle is defined as a cycle in a graph that passes through every vertex exactly once. A graph is outerplanar if it can be embedded in the plane such that all its vertices are on the outer face’s boundary. In such an embedding, denoted as H-embedding, the outer face forms a Hamiltonian cycle H_{G}=(x_{1},x_{2},\ldots,x_{n}) , and all other faces are inner faces. Moreover, such an embedding is called an outerplane graph. A graph is outerplanar if and only if it contains neither K_{4} nor K_{2,3} minor. In 1958, Grötzsch et al. [ 4 ] established the renowned Görtzsch’s Theorem, which asserts that every triangle-free planar graph is 3-colorable. Subsequently, Grünbaum [ 3 ] and Aksionov [ 1 ] extended this result by proving that planar graphs containing at most three triangles also admit 3-colorings. Their work further elucidated the extendability of colorings for 4- and 5-faces, marking a pivotal advancement in the field. This progress shifted research focus toward investigating 3-colorable planar graphs with triangular structures. La et al. [ 6 ] studied the 3-coloring extension under the constraint of planar graphs with at most one triangle and obtained the following results: Theorem 1.1 and Theorem 1.3 . Theorem 1.1 ( [ 6 ] ) . For any two independent vertices in a plane graph G, any precoloring assigned to them can be extended to a proper 3-coloring of the entire graph G . Theorem 1.2 ( [ 6 ] ) . If G is a plane graph with at most one triangle and v is a vertex of degree no more than 3 in a graph Q such that G=Q-v . When G contains at most one triangle and v is adjacent to at most two of its vertices. Then Q is 3-colorable. A graph G is K_{4}^{{}^{\prime}} -free if it contains no subdivision of K_{4} where exactly three edges incident to one vertex are subdivided, and the central vertex is degree 3 in G . For a proper 3-coloring of K_{4}^{{}^{\prime}} (See Feagure 1 ), v’s three neighbors cannot share the same color, as the subdivided edges enforce non-monochromatic on the neighbors of v constraints on the peripheral vertices. v Figure 1: The graph of K_{4}^{{}^{\prime}} . Theorem 1.3 ( [ 6 ] ) . If a K_{4}^{{}^{\prime}} -free plane graph G contains no more than one triangle, a precoloring with the same color of the neighbors of every vertex of degree at most 3 can be extended to a 3-coloring of G . In any 3-coloring of a 5-face, the color distribution follows a specific pattern: two vertices are assigned to one color, two to another, and the remaining vertex, the special vertex, receives the third color. The edge directly opposite this special vertex within the 5-face is designated as the special edge. Theorem 1.4 ( [ 1 , 3 ] ) . Let G be a plane graph. The following results hold. If G has at most three triangles, then the chromatic number of G is at most three; If G has at most one triangle, then • if G has a 4-face C , every 3-coloring of C can be extended to a 3-coloring of G ; • if G has a 5-face F , every 3-coloring of F can be extended to a 3-coloring of G if the special edge of F is not contained in a triangle. La et al. raised the three Problems 4.2, 4.3 and 4.4 at the end of the article [ 6 ] . Problem 4.4 [ 6 ] has been addressed in [ 1 , 3 ] for 5-face. In this paper, we attempt to address the first two problems in biconnected outerplanar graphs and then extend the results to outerplanar graphs. In this study, we propose a structure composed of two triangles sharing a common edge, which we designate as the “ diamond\ D ” (Figure 2 ). Within this configuration, two independent vertices u and v are constrained to share the same color in any proper 3-coloring. These vertices are termed “diamond vertices.” Notably, in Problem 4.2 [ 6 ] , the presence of the diamond structure enforces that u and v must adopt identical colors; otherwise, the graph admits no proper 3-coloring. u v Figure 2: The structure of “ diamond\ D ”. We establish new results on 3-precoloring extension properties for biconnected outerplanar graphs with at most two triangles and partially precolored vertices, formalized in Theorems 1.5 and 1.6 . Theorem 1.5 . Given a biconnected outerplane graph G containing a single triangle, any precoloring of three independent vertices can be extended to a 3-coloring of G . Theorem 1.6 . A biconnected outerplane graph G containing exactly two triangules satisfies the property that every 3-coloring assignment to any pair of independent vertices can be extended to a 3-coloring of G under the following three conditions. G forbids the diamond “ diamond\ D ” as a subgraph. G admits a diamond D as a subgraph, but any two precolored nonadjacent vertices share at most one vertex of D . G admits “ diamond\ D ” and the precolored two nonadjacent vertices are “ diamond\ vertices ”, then they must have the same precolored color. Since 1-connected outerplane graphs are subgraphs of certain 2-connected outerplane graphs obtained by edge additions, they share the same number of triangles. Corollary 1.7 . Consider a 1-connected outerplane graph G containing precisely one triangle. For any subset of three independent vertices in G , every proper precoloring of these vertices admits a completion to a 3-coloring of G .” Corollary 1.8 . Consider a 1-connected outerplane graph G containing precisely two triangless. For any subset of two independent vertices in G , every proper precoloring of these vertices admits a completion to a 3-coloring of G in the following three cases. G forbids the diamond “ diamond\ D ” as a subgraph. G admits a diamond D as a subgraph, but any two precolored nonadjacent vertices share at most one vertex of D . G admits “ diamond\ D ” and the precolored