Efficient algorithms for acyclic colorings of graphs
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.
- Algorithmic aspects of acyclic edge colorings
- On efficient coloring of chordless graphs
- Acyclic coloring of graphs
- Efficient bounds on a branch and bound algorithm for graph colouration
- Efficient algorithms for the edge-cover coloring problem
- An algorithm for optimal acyclic edge-colouring of cubic graphs
- Acyclic edge coloring of graphs
- scientific article; zbMATH DE number 956855
- Acyclic edge colorings of graphs
- Efficient algorithms for parameterized H-colorings
- Acyclic colorings of planar graphs
- An approach to the subgraph homeomorphism problem
- An Efficient Parallel Biconnectivity Algorithm
- An O(logn) parallel connectivity algorithm
- Efficient algorithms for vertex arboricity of planar graphs
- Finding Triconnected Components by Local Replacement
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 742981 (Why is no real title available?)
- Improved algorithms for graph four-connectivity
- Node-and edge-deletion NP-complete problems
- Parallel complexity of partitioning a planar graph into vertex-induced forests
- The point-arboricity of a graph
- The Point-Arboricity of Planar Graphs
- Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
- Acyclic edge-coloring using entropy compression
- Coloring graphs using two colors while avoiding monochromatic cycles
- Vertex arboricity of planar graphs without chordal 6-cycles
- Efficient algorithms for vertex arboricity of planar graphs
- New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
- Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
- A Game Theoretic Approach for Efficient Graph Coloring
- Efficient algorithms for the edge-cover coloring problem
- scientific article; zbMATH DE number 6469209 (Why is no real title available?)
- Acyclic and star colorings of cographs
- Heuristics for deciding collectively rational consumption behavior
- Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
- Some recent progress and applications in graph minor theory
This page was built for publication: Efficient algorithms for acyclic colorings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978502)
