1986/01/01 by Andrzej Proskurowski, Maciej M. Sysło · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Edge coloring #Outerplanar graph #Discrete mathematics #Vertex (graph theory) #Brooks' theorem #Complete coloring #Chromatic scale #Pathwidth #Graph #1-planar graph #Chordal graph #Graph power #Line graph
paper · doi:10.1137/0607016
openalex publication_date 1986/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
The problems of finding values of the chromatic number and the chromatic index of a graph are NP-hard even for some restricted classes of graphs. Every outerplanar graph has an associated tree structure which facilitates algorithmic treatment. Using that structure, we give an efficient algorithm to color the vertices of an outerplanar graph with the minimum number of colors. We also establish algorithmically the value of the chromatic index of an outerplanar graph. Our algorithms are based on systematic coloring of elements (vertices and edges, respectively) of adjacent faces.