Efficient algorithms for acyclic colorings of graphs
type: Item
instance of: scholarly article
title: Efficient algorithms for acyclic colorings of graphs
zbMATH Open document ID: 0941.68096
DOI: 10.1016/S0304-3975(97)00254-5
author: Yanyan Li
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
review text: An acyclic \(k\)-coloring of a graph \(G\) is a coloring of the vertices of \(G\) with at most \(k\) colors such that each color class induces an acyclic subgraph. The vertex arboricity \(a(G)\) of \(G\) is the minimum number \(k\) for which \(G\) has an acyclic \(k\)-coloring. Although the problem of computing \(a(G)\) is NP-hard, \(\rho(G)=1+\lfloor(\max\delta(G'))/2\rfloor\) is known to be a good upper bound on \(a(G)\), where the maximum is taken over all induced subgraphs \(G'\) of \(G\) and \(\delta(G')\) is the minimum degree of \(G'\). In this paper, we present the first linear-time algorithm for acyclic \(\rho(G)\)-colorings. We also give a sufficient condition under which an NC algorithm exists for acyclic \(\rho(G)\)-colorings. Using this condition, we obtain the first NC algorithm for acyclic \(\rho(G)\)-colorings of graphs without a \(K_{3,3}\) (or \(K_{5})\) minor.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1454282
zbMATH Keywords: vertex arboricity
zbMATH Keywords: acyclic colorings
zbMATH Keywords: parallel algorithms
zbMATH Keywords: sparse graphs
MaRDI profile type: Publication
cites work: An approach to the subgraph homeomorphism problem
cites work: The Point-Arboricity of Planar Graphs
cites work: The point-arboricity of a graph
cites work: Parallel complexity of partitioning a planar graph into vertex-induced forests
cites work: Finding Triconnected Components by Local Replacement
cites work: Q4198056
cites work: Acyclic colorings of planar graphs
cites work: Improved algorithms for graph four-connectivity
cites work: Q4763420
cites work: Efficient algorithms for vertex arboricity of planar graphs
cites work: An O(logn) parallel connectivity algorithm
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Node-and edge-deletion NP-complete problems
Recommended article: Algorithmic aspects of acyclic edge colorings
Recommended article: On Efficient Coloring of Chordless Graphs
Recommended article: Acyclic coloring of graphs
Recommended article: Efficient bounds on a branch and bound algorithm for graph colouration
Recommended article: Efficient algorithms for the edge-cover coloring problem
Recommended article: An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs
Recommended article: Acyclic edge coloring of graphs
Recommended article: Q5687263
Recommended article: Acyclic edge colorings of graphs
Recommended article: Q3424889
description: scientific article; zbMATH DE number 1454282