Precoloring 3-extension on outerplanar graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911490405040128 |
|---|---|
| author | Deng, Xingchao Zou, Beiyan Zhai, Hong |
| author_facet | Deng, Xingchao Zou, Beiyan Zhai, Hong |
| contents | The precoloring problem of a graph involves assigning colors to some vertices beforehand, and the objective is to determine whether it can be extended to a proper k-coloring of the entire graph. In 1958, Grotzsch proved that every triangle-free planar graph can be properly colored by three colors. One of the further generalizations of it is the recent result by Hoang La et al. in (Discrete Mathematics, 345(6) (2022), 112849 ). They proved that any two non-adjacent vertices and a face with a length at most four are precolored, the precolorings can be extended to a 3-coloring of the graph. In the paper, we consider precoloring extension of connected outerplanar graph with at most one or two triangles. Particularly, we show that precoloring of any two or three non-adjacent vertices can be extend to a 3-coloring of the whole graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05775 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Precoloring 3-extension on outerplanar graphs Deng, Xingchao Zou, Beiyan Zhai, Hong Combinatorics The precoloring problem of a graph involves assigning colors to some vertices beforehand, and the objective is to determine whether it can be extended to a proper k-coloring of the entire graph. In 1958, Grotzsch proved that every triangle-free planar graph can be properly colored by three colors. One of the further generalizations of it is the recent result by Hoang La et al. in (Discrete Mathematics, 345(6) (2022), 112849 ). They proved that any two non-adjacent vertices and a face with a length at most four are precolored, the precolorings can be extended to a 3-coloring of the graph. In the paper, we consider precoloring extension of connected outerplanar graph with at most one or two triangles. Particularly, we show that precoloring of any two or three non-adjacent vertices can be extend to a 3-coloring of the whole graph. |
| title | Precoloring 3-extension on outerplanar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.05775 |