Efficient algorithms for acyclic colorings of graphs

DOI10.1016/S0304-3975(97)00254-5zbMath0941.68096MaRDI QIDQ1978502

Yanyan Li

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmssparse graphsvertex arboricityacyclic colorings

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Some recent progress and applications in graph minor theory, Heuristics for deciding collectively rational consumption behavior, Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles, Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application., Vertex arboricity of planar graphs without chordal 6-cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Improved algorithms for graph four-connectivity
• An approach to the subgraph homeomorphism problem
• Parallel complexity of partitioning a planar graph into vertex-induced forests
• The point-arboricity of a graph
• Efficient algorithms for vertex arboricity of planar graphs
• An Efficient Parallel Biconnectivity Algorithm
• An O(logn) parallel connectivity algorithm
• Finding Triconnected Components by Local Replacement
• Node-and edge-deletion NP-complete problems
• The Point-Arboricity of Planar Graphs
• Acyclic colorings of planar graphs