Facial Rainbow Coloring of Plane Graphs
A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G)...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2019-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2047 |
| _version_ | 1797757737957851136 |
|---|---|
| author | Jendroľ Stanislav Kekeňáková Lucia |
| author_facet | Jendroľ Stanislav Kekeňáková Lucia |
| author_sort | Jendroľ Stanislav |
| collection | DOAJ |
| description | A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G) denote the order of a longest facial path in G. In the present note we prove that rb(T)≤⌊32L(T)⌋$rb(T) \le \left\lfloor {{3 \over 2}L(T)} \right\rfloor$ for any tree T and rb(G)≤⌈53L(G)⌉$rb(G) \le \left\lceil {{5 \over 3}L(G)} \right\rceil$ for arbitrary simple graph G. The upper bound for trees is tight. For any simple 3-connected plane graph G we have rb(G) ≤ L(G) + 5. |
| first_indexed | 2024-03-12T18:19:54Z |
| format | Article |
| id | doaj.art-2727cf2f6bd0436cb04bfd5ff2724be0 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:54Z |
| publishDate | 2019-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-2727cf2f6bd0436cb04bfd5ff2724be02023-08-02T08:59:09ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922019-11-0139488989710.7151/dmgt.2047dmgt.2047Facial Rainbow Coloring of Plane GraphsJendroľ Stanislav0Kekeňáková Lucia1Institute of Mathematics, Faculty of Science, Šafárik University, Jesenná 5, 040 01Košice, SlovakiaInstitute of Mathematics, Faculty of Science, Šafárik University, Jesenná 5, 040 01Košice, SlovakiaA vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G) denote the order of a longest facial path in G. In the present note we prove that rb(T)≤⌊32L(T)⌋$rb(T) \le \left\lfloor {{3 \over 2}L(T)} \right\rfloor$ for any tree T and rb(G)≤⌈53L(G)⌉$rb(G) \le \left\lceil {{5 \over 3}L(G)} \right\rceil$ for arbitrary simple graph G. The upper bound for trees is tight. For any simple 3-connected plane graph G we have rb(G) ≤ L(G) + 5.https://doi.org/10.7151/dmgt.2047cyclic coloringrainbow coloringplane graphs05c1005c15 |
| spellingShingle | Jendroľ Stanislav Kekeňáková Lucia Facial Rainbow Coloring of Plane Graphs Discussiones Mathematicae Graph Theory cyclic coloring rainbow coloring plane graphs 05c10 05c15 |
| title | Facial Rainbow Coloring of Plane Graphs |
| title_full | Facial Rainbow Coloring of Plane Graphs |
| title_fullStr | Facial Rainbow Coloring of Plane Graphs |
| title_full_unstemmed | Facial Rainbow Coloring of Plane Graphs |
| title_short | Facial Rainbow Coloring of Plane Graphs |
| title_sort | facial rainbow coloring of plane graphs |
| topic | cyclic coloring rainbow coloring plane graphs 05c10 05c15 |
| url | https://doi.org/10.7151/dmgt.2047 |
| work_keys_str_mv | AT jendrolstanislav facialrainbowcoloringofplanegraphs AT kekenakovalucia facialrainbowcoloringofplanegraphs |