Odd facial colorings of acyclic plane graphs
| Main Authors: | Czap, Július; Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice, Němcovej 32, 04001 Košice, Slovakia, Šugerek, Peter; Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Košice, Němcovej 32, 04001 Košice, Slovakia |
|---|---|
| Other Authors: | Slovak Research and Development Agency |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/775 https://www.ejgta.org/index.php/ejgta/article/view/775/pdf_183 |
Daftar Isi:
- Let G be a connected plane graph with vertex set V and edge set E. For X ∈ {V, E, V ∪ E}, two elements of X are facially adjacent in G if they are incident elements, adjacent vertices, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of G). A coloring of G is facial with respect to X if there is a coloring of elements of X such that facially adjacent elements of X receive different colors. A facial coloring of G is odd if for every face f and every color c, either no element or an odd number of elements incident with f is colored by c. In this paper we investigate odd facial colorings of trees. The main results of this paper are the following: (i) Every tree admits an odd facial vertex-coloring with at most 4 colors; (ii) Only one tree needs 6 colors, the other trees admit an odd facial edge-coloring with at most 5 colors; and (iii) Every tree admits an odd facial total-coloring with at most 5 colors. Moreover, all these bounds are tight.