Acyclic colorings of planar graphs

DOI10.1007/BF02764716zbMath0265.05103OpenAlexW2143263735WikidataQ55966840 ScholiaQ55966840MaRDI QIDQ5921616

Branko Grünbaum

Publication date: 1973

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02764716

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (only showing first 100 items - show all)

Acyclically 4-colorable triangulations ⋮ Equitable vertex arboricity of subcubic graphs ⋮ Improved bounds on the generalized acyclic chromatic number ⋮ On purely tree-colorable planar graphs ⋮ Acyclic coloring of graphs with some girth restriction ⋮ Good and semi-strong colorings of oriented planar graphs ⋮ A polyhedral investigation of star colorings ⋮ Acyclic colorings of subcubic graphs ⋮ List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles ⋮ New bounds for the acyclic chromatic index ⋮ I,F-partitions of sparse graphs ⋮ Acyclic colorings of graphs with bounded degree ⋮ Acyclic colorings of products of trees ⋮ Analysis of a heuristic for acyclic edge colouring ⋮ Colorings and girth of oriented planar graphs ⋮ Star chromatic bounds ⋮ Strongly polynomial sequences as interpretations ⋮ Star coloring of graphs with girth at least five ⋮ List star edge-coloring of subcubic graphs ⋮ Parmenides reloaded ⋮ From change to spacetime: an eleatic journey ⋮ On acyclic colorings of graphs on surfaces ⋮ Acyclic edge coloring of planar graphs without small cycles ⋮ Acyclic coloring with few division vertices ⋮ Acyclic coloring of graphs without bichromatic long path ⋮ Acyclic 4-choosability of planar graphs ⋮ Acyclic colorings of graph subdivisions revisited ⋮ On linear coloring of planar graphs with small girth ⋮ Star coloring of cubic graphs ⋮ Improved upper bounds on acyclic edge colorings ⋮ Vertex-arboricity of planar graphs without intersecting triangles ⋮ Improved bounds on linear coloring of plane graphs ⋮ Acyclic vertex coloring of graphs of maximum degree 5 ⋮ On acyclic edge coloring of toroidal graphs ⋮ Graphs with maximum degree \(6\) are acyclically \(11\)-colorable ⋮ Acyclic edge coloring of planar graphs with \(\varDelta\) colors ⋮ \(k\)-forested coloring of planar graphs with large girth ⋮ List star edge coloring of sparse graphs ⋮ Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs ⋮ Planar graphs without 4- and 5-cycles are acyclically 4-choosable ⋮ Star coloring of certain graph classes ⋮ Weights of induced subgraphs in \(K_{1,r}\)-free graphs ⋮ From the plane to higher surfaces ⋮ Frugal, acyclic and star colourings of graphs ⋮ Acyclic and star colorings of cographs ⋮ Characterization of forbidden subgraphs for bounded star chromatic number ⋮ Randomly colouring graphs (a combinatorial view) ⋮ A spatially-VSL gravity model with 1-PN limit of GRT ⋮ Oriented colourings of graphs with maximum degree three and four ⋮ Maximizing and minimizing the number of generalized colorings of trees ⋮ Acyclic total colorings of planar graphs without \(l\) cycles ⋮ Acyclic 6-choosability of planar graphs without adjacent short cycles ⋮ Linear and 2-frugal choosability of graphs of small maximum average degree ⋮ Linear choosability of graphs ⋮ Degenerate and star colorings of graphs on surfaces ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\) ⋮ An introduction to the discharging method via graph coloring ⋮ List vertex-arboricity of planar graphs without intersecting 5-cycles ⋮ On the complexity of generalized chromatic polynomials ⋮ List star chromatic index of sparse graphs ⋮ Nonrepetitive colouring via entropy compression ⋮ Acyclic improper colourings of graphs with bounded maximum degree ⋮ List star edge coloring of \(k\)-degenerate graphs ⋮ New upper bounds on linear coloring of planar graphs ⋮ On chromatic numbers of two extensions of planar graphs ⋮ On Reichenbach's causal betweenness ⋮ The complexity of some acyclic improper colourings ⋮ Acyclically 3-colorable planar graphs ⋮ \(\mathcal Q\)-Ramsey classes of graphs ⋮ Strengthening of a theorem about 3-polytopes ⋮ Acyclic colorings of locally planar graphs ⋮ About acyclic edge colourings of planar graphs ⋮ Acyclic 3-choosability of sparse graphs with girth at least 7 ⋮ Note to the paper of Grünbaum on acyclic colorings ⋮ Optimal acyclic edge colouring of grid like graphs ⋮ Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles ⋮ Acyclic 4-choosability of planar graphs without adjacent short cycles ⋮ On acyclic 4-choosability of planar graphs without short cycles ⋮ List total arboricity of 2-degenerate graphs ⋮ Every planar graph has an acyclic 7-coloring ⋮ On acyclic edge-coloring of complete bipartite graphs ⋮ Acyclic edge coloring of subcubic graphs ⋮ On acyclic colorings of planar graphs ⋮ Acyclic and \(k\)-distance coloring of the grid ⋮ On the acyclic chromatic number of Hamming graphs ⋮ \(k\)-forested choosability of planar graphs and sparse graphs ⋮ Acyclic edge coloring of planar graphs with large girth ⋮ Linear coloring of graphs embeddable in a surface of nonnegative characteristic ⋮ Acyclic edge colorings of planar graphs and series parallel graphs ⋮ Time, quantum mechanics, and decoherence. ⋮ A note on acyclic edge coloring of complete bipartite graphs ⋮ Linear coloring of planar graphs with large girth ⋮ Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles ⋮ Acyclic \(k\)-strong coloring of maps on surfaces ⋮ Antisymmetric flows and strong colourings of oriented graphs ⋮ A bound for the game chromatic number of graphs ⋮ Vertex colorings with a distance restriction ⋮ Minimum feedback vertex set and acyclic coloring. ⋮ Black, white and gray: Quine on convention

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The point-arboricity of a graph
• Graphs with forbidden subgraphs
• Shortness exponents of families of graphs
• Grötzsch's theorem on 3-colorings
• Quelques consequences simples de la formule d'Euler
• Graph Theory and Probability
• Hamilton Circuits of Convex Trivalent Polyhedra (Up to 18 Vertices)
• On Partitioning Planar Graphs
• The Point-Arboricity of Planar Graphs
• An Analogue to the Heawood Map-Colouring Problem
• $B$-sets and coloring problems
• A 4-Color Theorem for Toroidal Graphs
• The Point Partition Numbers of Closed 2-Manifolds

This page was built for publication: Acyclic colorings of planar graphs