Acyclically 3-colorable planar graphs

DOI10.1007/s10878-011-9385-3zbMath1258.05025OpenAlexW2089322292MaRDI QIDQ695319

Fabrizio Frati, Patrizio Angelini

Publication date: 21 December 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-011-9385-3

zbMATH Keywords

planar graphscubic graphsacyclic coloringtriconnectivity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items

A note on the minimum number of choosability of planar graphs, List edge and list total coloring of planar graphs with maximum degree 8, An efficient case for computing minimum linear arboricity with small maximum degree, Acyclic coloring with few division vertices, Minimum number of disjoint linear forests covering a planar graph, Hardness transitions and uniqueness of acyclic colouring, Unnamed Item, Acyclic 3-coloring of generalized Petersen graphs

Uses Software

• ColPack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic colorings of subcubic graphs
• Note to the paper of Grünbaum on acyclic colorings
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• On acyclic colorings of planar graphs
• Every planar graph has an acyclic 8-coloring
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
• Acyclically 3-Colorable Planar Graphs
• Acyclic Colourings of Planar Graphs with Large Girth
• The Recognition of Series Parallel Digraphs
• Acyclic coloring of graphs
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Layout of Graphs with Bounded Tree-Width
• Acyclic colorings of planar graphs