<abstract xmlns="http://www.w3.org/1999/xhtml">A graph <italic>G</italic> = (<italic>V;E</italic>) is word-representable if there is a word <italic>w</italic> over the alphabet <italic>V</italic> such that <italic>x</italic> and <italic>y</italic> alternate in <italic>w</italic> if and only if the edge (<italic>x; y</italic>) is in <italic>G</italic>. It is known [6] that all 3-colourable graphs are word-representable, while among those with a higher chromatic number some are word-representable while others are not.There has been some recent research on the word-representability of polyomino triangulations. Akrobotu et al. [1] showed that a triangulation of a convex polyomino is word-representable if and only if it is 3-colourable; and Glen and Kitaev [5] extended this result to the case of a rectangular polyomino triangulation when a single domino tile is allowed.It was shown in [4] that a near-triangulation is 3-colourable if and only if it is internally even. This paper provides a much shorter and more elegant proof of this fact, and also shows that near-triangulations are in fact a generalization of the polyomino triangulations studied in [1] and [5], and so we generalize the results of these two papers, and solve all open problems stated in [5].</abstract>

A graph G = (V;E) is word-representable if there is a word w over the alphabet V such that x and y alternate in w if and only if the edge (x; y) is in G. It is known [6] that all 3-colourable graphs are word-representable, while among those with a higher chromatic number some are word-representable while others are not.There has been some recent research on the word-representability of polyomino triangulations. Akrobotu et al. [1] showed that a triangulation of a convex polyomino is word-representable if and only if it is 3-colourable; and Glen and Kitaev [5] extended this result to the case of a rectangular polyomino triangulation when a single domino tile is allowed.It was shown in [4] that a near-triangulation is 3-colourable if and only if it is internally even. This paper provides a much shorter and more elegant proof of this fact, and also shows that near-triangulations are in fact a generalization of the polyomino triangulations studied in [1] and [5], and so we generalize the results of these two papers, and solve all open problems stated in [5].

Colourability and word-representability of near-triangulations

Department of Computer and Information Sciences

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Colourability and word-representability of near-triangulations"}

A graph G = (V;E) is word-representable if there is a word w over the alphabet V such that x and y alternate in w if and only if the edge (x; y) is in G. It is...

Colourability and word-representability of near-triangulations

Published Online: Nov 01, 2019

Page range: 70 - 76

Received: Sep 28, 2018

Accepted: Sep 09, 2019

DOI: https://doi.org/10.1515/puma-2015-0032

Keywords
word-representable graph, 3-colorability, polyomino, triangulation

© 2019 Marc Elliot Glen, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Colourability and word-representability of near-triangulations

Published Online: Nov 01, 2019

Page range: 70 - 76

Received: Sep 28, 2018

Accepted: Sep 09, 2019

DOI: https://doi.org/10.1515/puma-2015-0032

Keywordsword-representable graph, 3-colorability, polyomino, triangulation

© 2019 Marc Elliot Glen, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
word-representable graph, 3-colorability, polyomino, triangulation