Acyclic colorings of planar graphs

From MaRDI portal

Publication:5921616

Jump to:navigation, search

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

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 ⋮ Acyclic choosability of graphs with bounded degree ⋮ Construction of acyclically 4-colourable planar triangulations with minimum degree 4 ⋮ Paths with restricted degrees of their vertices in planar graphs ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ A sufficient condition for planar graphs to be acyclically 5-choosable ⋮ A new approach on locally checkable problems ⋮ Plurigraph coloring and scheduling problems ⋮ Acyclic list 7‐coloring of planar graphs ⋮ Acyclic 5-choosability of planar graphs without adjacent short cycles ⋮ Acyclic coloring of graphs of maximum degree five: nine colors are enough ⋮ Coloring parameters for graphs on surfaces ⋮ Star chromatic number of some graphs ⋮ Coloring 3-power of 3-subdivision of subcubic graph ⋮ Star Edge Coloring of Some Classes of Graphs ⋮ Logic of simultaneity ⋮ On homomorphisms of oriented graphs with respect to the push operation ⋮ On star 5-colorings of sparse graphs ⋮ Acyclic coloring of graphs with maximum degree 7 ⋮ On star coloring of modular product of graphs ⋮ Acyclic coloring of claw-free graphs with small degree ⋮ Star edge-coloring of square grids ⋮ List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs ⋮ Structural Properties of Planar Maps with the Minimal Degree 5 ⋮ A note on a conjecture of star chromatic index for outerplanar graphs ⋮ On Light Edges and Triangles in Planar Graphs of Minimum Degree Five ⋮ An improved upper bound for the acyclic chromatic number of 1-planar graphs ⋮ The arrow of time: From universe time-asymmetry to local irreversible processes ⋮ On b-acyclic chromatic number of a graph ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ The method of coloring in graphs and its application ⋮ On nowhere dense graphs ⋮ Acyclic 4-choosability of planar graphs without intersecting short cycles ⋮ Every toroidal graph is acyclically 8-choosable ⋮ Linear colorings of subcubic graphs ⋮ Acyclic vertex coloring of graphs of maximum degree six ⋮ Star edge coloring of corona product of path and wheel graph families ⋮ Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large ⋮ On star coloring of degree splitting of join graphs ⋮ Acyclic 4-choosability of planar graphs without 4-cycles ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Improved bounds on acyclic edge colouring ⋮ An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs ⋮ 6-Star-Coloring of Subcubic Graphs ⋮ Acyclic edge colorings of graphs ⋮ Optimal acyclic edge‐coloring of cubic graphs ⋮ Acyclic Edge Coloring of Triangle‐Free Planar Graphs ⋮ Star Chromatic Index ⋮ Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles ⋮ Acyclic edge coloring of planar graphs without cycles of specific lengths ⋮ A polyhedral study of the acyclic coloring problem ⋮ Acyclic improper choosability of subcubic graphs ⋮ Weak acyclic coloring and asymmetric coloring games ⋮ Unnamed Item ⋮ The linear \(t\)-colorings of Sierpiński-like graphs ⋮ Star list chromatic number of planar subcubic graphs ⋮ Bounds on the generalised acyclic chromatic numbers of bounded degree graphs ⋮ Acyclic improper colouring of graphs with maximum degree 4 ⋮ On acyclic colorings of planar graphs. (Reprint) ⋮ Equitable partition of planar graphs ⋮ d‐Regular graphs of acyclic chromatic index at least d+2 ⋮ Linear choosability of sparse graphs ⋮ Circular vertex arboricity ⋮ Acyclic chromatic indices of planar graphs with large girth ⋮ Acyclic edge chromatic number of outerplanar graphs ⋮ An acyclic analogue to Heawood's theorem ⋮ Acyclic \(L\)-coloring of graphs with maximum degrees 5 and 6 ⋮ Game coloring the Cartesian product of graphs ⋮ Star coloring bipartite planar graphs ⋮ On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9 ⋮ Upper bounds on list star chromatic index of sparse graphs ⋮ Unnamed Item ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Acyclic 6-choosability of planar graphs without 5-cycles and adjacent 4-cycles ⋮ Coloring graphs without bichromatic cycles or paths ⋮ Acyclic dominating partitions ⋮ Acyclic coloring of graphs and entropy compression method ⋮ Bounds on vertex colorings with restrictions on the union of color classes ⋮ Unnamed Item ⋮ Acyclic edge colourings of graphs with large girth ⋮ Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope ⋮ Star coloring outerplanar bipartite graphs ⋮ On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets ⋮ On acyclically 4-colorable maximal planar graphs ⋮ Acyclic edge coloring of graphs with maximum degree 4 ⋮ Planar graphs without 4-cycles are acyclically 6-choosable ⋮ Star coloring of sparse graphs ⋮ Acyclic Vertex Coloring of Graphs of Maximum Degree Six ⋮ Acyclic coloring of graphs with maximum degree at most six ⋮ Note on a paper of B. Grünbaum on acyclic colorings ⋮ Acyclic edge coloring of 2-degenerate graphs ⋮ Acyclic coloring of IC-planar graphs ⋮ Planar graphs without 4, 5 and 8-cycles are acyclically 4-choosable ⋮ Introduction to dominated edge chromatic number of a graph ⋮ ON STAR COLORING OF DEGREE SPLITTING OF COMB PRODUCT GRAPHS ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ On vertex rankings of graphs and its relatives ⋮ The \(r\)-acyclic chromatic number of planar graphs ⋮ A Conjecture of Borodin and a Coloring of Grünbaum ⋮ Star chromatic number of Harary graphs ⋮ The local cut lemma ⋮ Acyclic chromatic index of chordless graphs ⋮ Star chromatic number of some graph products ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ The complexity of star colouring in bounded degree graphs and regular graphs ⋮ Injective edge-coloring of subcubic graphs ⋮ On structural parameterizations of star coloring ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Upper bounds on the acyclic chromatic index of degenerate graphs ⋮ Partitioning kite‐free planar graphs into two forests ⋮ Acyclic 5-choosability of planar graphs without 4-cycles ⋮ Acyclic colouring of 1-planar graphs ⋮ A polyhedral study of the acyclic coloring problem ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ Acyclic dominating partitions

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5921616&oldid=15311307"