Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs

DOI10.1007/978-3-642-25870-1_11zbMath1341.05068OpenAlexW152886480MaRDI QIDQ3104769

Ichiro Suzuki, Christine T. Cheng, Eric J. McDermid

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_11

zbMATH Keywords

acyclic coloringsmaximum planar subgraphmaximum induced planar subgraphsubcubic claw-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76)

Related Items (5)

Hardness transitions and uniqueness of acyclic colouring ⋮ Unnamed Item ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ Acyclic, star, and injective colouring: bounding the diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic colorings of subcubic graphs
• Algorithmic aspects of acyclic edge colorings
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Disjoint triangles of a cubic line graph
• Planarization and fragmentability of some classes of graphs
• On maximum planar induced subgraphs
• Planarizing Graphs - A Survey and Annotated Bibliography
• Graphs with maximum degree 5 are acyclically 7-colorable
• Edge-Deletion Problems
• Acyclic coloring of graphs
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Node-and edge-deletion NP-complete problems
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

This page was built for publication: Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs