Acyclically 3-colorable planar graphs

DOI10.1007/S10878-011-9385-3MaRDI QIDQ695319zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Fabrizio Frati

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

cubic graphsplanar graphsacyclic coloringtriconnectivity

Mathematics Subject Classification ID

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

Recommendations

• Acyclically 3-colorable planar graphs
• Acyclic colorings of planar graphs
• Acyclic edge-coloring of planar graphs
• 3-hued coloring of planar graphs
• Cycle adjacency of planar graphs and 3-colourability
• Acyclic edge coloring of triangle-free planar graphs
• scientific article; zbMATH DE number 5584824
• A sufficient condition for planar graphs to be 3-colorable
• On 3-colorings of plane graphs
• Acyclic total colorings of planar graphs.

Cites work

• scientific article; zbMATH DE number 3639666 (Why is no real title available?)
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• scientific article; zbMATH DE number 2159660 (Why is no real title available?)
• scientific article; zbMATH DE number 2090688 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Acyclic Colourings of Planar Graphs with Large Girth
• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Acyclic colorings of subcubic graphs
• Acyclically 3-colorable planar graphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Efficient computation of sparse hessians using coloring and automatic differentiation
• Every planar graph has an acyclic 8-coloring
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Negative results on acyclic improper colorings
• Note to the paper of Grünbaum on acyclic colorings
• On acyclic colorings of planar graphs
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• The Recognition of Series Parallel Digraphs

Cited in

(12)

• Acyclic 3-coloring of generalized Petersen graphs
• Planarization and acyclic colorings of subcubic claw-free graphs
• A note on the minimum number of choosability of planar graphs
• Acyclic coloring with few division vertices
• Minimum number of disjoint linear forests covering a planar graph
• Hardness transitions and uniqueness of acyclic colouring
• List edge and list total coloring of planar graphs with maximum degree 8
• Cycle adjacency of planar graphs and 3-colourability
• Acyclically 3-colorable planar graphs
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• An efficient case for computing minimum linear arboricity with small maximum degree
• Efficient algorithms for vertex arboricity of planar graphs

Describes a project that uses

Uses Software

• ColPack

This page was built for publication: Acyclically 3-colorable planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q695319)