Name
Abstract | ||
|---|---|---|
A graph G is uniquely k-colourable if the chromatic number of G is k and G has only one k-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 1977, pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 1977, pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graph G has at most 4 triangles then G has two adjacent triangles. Furthermore, for any <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" href=\"gcom_a_1167196_ilm0001.gif\"/</inline-formula>, we construct a uniquely 3-colourable planar graph with k triangles and without adjacent triangles. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1080/00207160.2016.1167196 | Int. J. Comput. Math. |
Keywords | Field | DocType |
Planar graph, unique colouring, uniquely 3-colourable planar graph, construction | Discrete mathematics,Outerplanar graph,Combinatorics,Graph power,Forbidden graph characterization,Planar straight-line graph,Book embedding,Nested triangles graph,Mathematics,Planar graph,Complement graph | Journal |
Volume | Issue | ISSN |
94 | 5 | 0020-7160 |
Citations | PageRank | References |
1 | 0.37 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zepeng Li | 1 | 20 | 9.07 |
| Enqiang Zhu | 2 | 25 | 11.99 |
| Zehui Shao | 3 | 119 | 30.98 |
| Jin Xu | 4 | 230 | 45.13 |