Grünbaum colorings extended to non-facial 3-cycles
<p class="p1"><span>We consider the question of when a triangulation with a Grünbaum coloring can be edge-colored with three colors such that the non-facial 3-cycles also receive all three colors; we will call this a </span><em>strong Grünbaum coloring</em><...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2022-03-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/1458 |
| _version_ | 1811335809180106752 |
|---|---|
| author | sarah-marie belcastro Ruth Haas |
| author_facet | sarah-marie belcastro Ruth Haas |
| author_sort | sarah-marie belcastro |
| collection | DOAJ |
| description | <p class="p1"><span>We consider the question of when a triangulation with a Grünbaum coloring can be edge-colored with three colors such that the non-facial 3-cycles also receive all three colors; we will call this a </span><em>strong Grünbaum coloring</em><span>. It turns out that for the sphere, every triangulation has a strong Grünbaum coloring, and that the presence of a </span><span class="math inline"><em>K</em><sub>5</sub></span><span> subgraph prohibits a strong Grünbaum coloring, but that </span><span class="math inline"><em>K</em><sub>5</sub></span><span> is not the only such barrier. We investigate the ramifications of these facts. We also show that for every other topological surface there exist triangulations with a strong Grünbaum coloring and triangulations that have Grünbaum colorings but that cannot have a strong Grünbaum coloring. Finally, we reframe strong Grünbaum colorings as certain hypergraph edge colorings, and raise the question of how many colors are needed to achieve an edge coloring such that both facial and non-facial 3-cycles receive three colors.</span></p> |
| first_indexed | 2024-04-13T17:29:25Z |
| format | Article |
| id | doaj.art-3fa39c6b5ad4478fa0401cf52116425a |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-13T17:29:25Z |
| publishDate | 2022-03-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-3fa39c6b5ad4478fa0401cf52116425a2022-12-22T02:37:37ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872022-03-0110110.5614/ejgta.2022.10.1.13254Grünbaum colorings extended to non-facial 3-cyclessarah-marie belcastro0Ruth Haas1Mathematical Staircase, Inc. and Smith CollegeUniversity of Hawaii at Manoa<p class="p1"><span>We consider the question of when a triangulation with a Grünbaum coloring can be edge-colored with three colors such that the non-facial 3-cycles also receive all three colors; we will call this a </span><em>strong Grünbaum coloring</em><span>. It turns out that for the sphere, every triangulation has a strong Grünbaum coloring, and that the presence of a </span><span class="math inline"><em>K</em><sub>5</sub></span><span> subgraph prohibits a strong Grünbaum coloring, but that </span><span class="math inline"><em>K</em><sub>5</sub></span><span> is not the only such barrier. We investigate the ramifications of these facts. We also show that for every other topological surface there exist triangulations with a strong Grünbaum coloring and triangulations that have Grünbaum colorings but that cannot have a strong Grünbaum coloring. Finally, we reframe strong Grünbaum colorings as certain hypergraph edge colorings, and raise the question of how many colors are needed to achieve an edge coloring such that both facial and non-facial 3-cycles receive three colors.</span></p>https://www.ejgta.org/index.php/ejgta/article/view/1458embedding, edge coloring, grünbaum coloring, triangulation |
| spellingShingle | sarah-marie belcastro Ruth Haas Grünbaum colorings extended to non-facial 3-cycles Electronic Journal of Graph Theory and Applications embedding, edge coloring, grünbaum coloring, triangulation |
| title | Grünbaum colorings extended to non-facial 3-cycles |
| title_full | Grünbaum colorings extended to non-facial 3-cycles |
| title_fullStr | Grünbaum colorings extended to non-facial 3-cycles |
| title_full_unstemmed | Grünbaum colorings extended to non-facial 3-cycles |
| title_short | Grünbaum colorings extended to non-facial 3-cycles |
| title_sort | grunbaum colorings extended to non facial 3 cycles |
| topic | embedding, edge coloring, grünbaum coloring, triangulation |
| url | https://www.ejgta.org/index.php/ejgta/article/view/1458 |
| work_keys_str_mv | AT sarahmariebelcastro grunbaumcoloringsextendedtononfacial3cycles AT ruthhaas grunbaumcoloringsextendedtononfacial3cycles |