Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs
We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40+1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-09-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1708 |
| _version_ | 1827840310784294912 |
|---|---|
| author | Borodin Oleg V. Ivanova Anna O. |
| author_facet | Borodin Oleg V. Ivanova Anna O. |
| author_sort | Borodin Oleg V. |
| collection | DOAJ |
| description | We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40+1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆. |
| first_indexed | 2024-03-12T07:32:24Z |
| format | Article |
| id | doaj.art-1360e737390f48a8bf93c9374bd1e10e |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:24Z |
| publishDate | 2013-09-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-1360e737390f48a8bf93c9374bd1e10e2023-09-02T21:43:05ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-09-0133475977010.7151/dmgt.1708Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar GraphsBorodin Oleg V.0Ivanova Anna O.1Institute of Mathematics Siberian Branch of the Russian Academy of SciencesInstitute of Mathematics of Ammosov North-Eastern Federal University Yakutsk, 677891, RussiaWe prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40+1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.https://doi.org/10.7151/dmgt.1708planar graphedge coloring2-distance coloringstrong edgecoloring |
| spellingShingle | Borodin Oleg V. Ivanova Anna O. Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs Discussiones Mathematicae Graph Theory planar graph edge coloring 2-distance coloring strong edgecoloring |
| title | Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs |
| title_full | Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs |
| title_fullStr | Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs |
| title_full_unstemmed | Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs |
| title_short | Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs |
| title_sort | precise upper bound for the strong edge chromatic number of sparse planar graphs |
| topic | planar graph edge coloring 2-distance coloring strong edgecoloring |
| url | https://doi.org/10.7151/dmgt.1708 |
| work_keys_str_mv | AT borodinolegv preciseupperboundforthestrongedgechromaticnumberofsparseplanargraphs AT ivanovaannao preciseupperboundforthestrongedgechromaticnumberofsparseplanargraphs |