On acyclic colorings of planar graphs

From MaRDI portal

Publication:1257487

Jump to:navigation, search

DOI10.1016/0012-365X(79)90077-3zbMath0406.05031OpenAlexW4213087285WikidataQ56390796 ScholiaQ56390796MaRDI QIDQ1257487

Oleg V. Borodin

Publication date: 1979

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(79)90077-3

zbMATH Keywords

Acyclic Colorings of Planar Graphs Vertex Coloring

Mathematics Subject Classification ID

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

Related Items

A sufficient condition for planar graphs to be acyclically 5-choosable, Acyclic list 7‐coloring of planar graphs, Acyclic 5-choosability of planar graphs without adjacent short cycles, Coloring parameters for graphs on surfaces, Primal-dual approximation algorithms for feedback problems in planar graphs, Star chromatic number of some graphs, Hyperbolic families and coloring graphs on surfaces, 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, Robust Connectivity of Graphs on Surfaces, Universal targets for homomorphisms of edge-colored graphs, The \(k\)-strong induced arboricity of a graph, Analogues of cliques for \((m,n)\)-colored mixed graphs, Improved upper bound for the degenerate and star chromatic numbers of graphs, Graph colorings with restricted bicolored subgraphs: II. The graph coloring game, Injective edge-coloring of subcubic graphs, On b-acyclic chromatic number of a graph, Grad and classes with bounded expansion. I: Decompositions, Hardness transitions and uniqueness of acyclic colouring, On the adaptable chromatic number of graphs, Unnamed Item, The method of coloring in graphs and its application, Decomposing a triangle-free planar graph into a forest and a subcubic forest, Acyclic 4-choosability of planar graphs without intersecting short cycles, On Chromatic Number of Colored Mixed Graphs, Every toroidal graph is acyclically 8-choosable, Acyclic vertex coloring of graphs of maximum degree six, Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large, Acyclic 5-choosability of planar graphs without 4-cycles, Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs, Star coloring planar graphs from small lists, Acyclic 5-choosability of planar graphs without 4-cycles, 6-Star-Coloring of Subcubic Graphs, Acyclic polynomials of graphs, Acyclic Edge Coloring of Triangle‐Free Planar Graphs, Homomorphisms of 2-edge-colored graphs, Homomorphisms of 2-edge-colored graphs, The game of arboricity, Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles, Weak acyclic coloring and asymmetric coloring games, Tree-depth, subgraph coloring and homomorphism bounds, Bounds on the generalised acyclic chromatic numbers of bounded degree graphs, Acyclic edge chromatic number of outerplanar graphs, Acyclic colouring of 1-planar graphs, Game coloring the Cartesian product of graphs, Star coloring bipartite planar graphs, A polyhedral study of the acyclic coloring problem, Dimension and height for posets with planar cover graphs., Acyclic subgraphs of planar digraphs, Smaller universal targets for homomorphisms of edge-colored graphs, Acyclic dominating partitions, SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs, Acyclic dominating partitions, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope, Unnamed Item, Planar Graphs of Bounded Degree Have Bounded Queue Number, Acyclic edge coloring of graphs with maximum degree 4, Planar graphs without 4-cycles are acyclically 6-choosable, Acyclic Vertex Coloring of Graphs of Maximum Degree Six, Acyclic edge coloring of 2-degenerate graphs, Acyclic choosability of planar graphs: a Steinberg like approach, Planar graphs without 4, 5 and 8-cycles are acyclically 4-choosable, Unique list-colourability and the fixing chromatic number of graphs, On some arboricities in planar graphs, A Conjecture of Borodin and a Coloring of Grünbaum, Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets, Homomorphisms of Signed Graphs, Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs, Acyclic choosability of graphs with bounded degree, Acyclically 4-colorable triangulations, Equitable vertex arboricity of subcubic graphs, Hamiltonicity and generalised total colourings of planar graphs, Homomorphisms and colourings of oriented graphs: an updated survey, Good and semi-strong colorings of oriented planar graphs, Induced and weak induced arboricities, Oriented colorings of triangle-free planar graphs, Acyclic colorings of subcubic graphs, An oriented 6-coloring of planar graphs with girth at least 9, Caterpillar arboricity of planar graphs, I,F-partitions of sparse graphs, Separation dimension of graphs and hypergraphs, Acyclic colorings of products of trees, Acyclic coloring of graphs of maximum degree five: nine colors are enough, A sufficient condition for a planar graph to be \((\mathcal{F},\mathcal{F}_2)\)-partitionable, Colorings and girth of oriented planar graphs, A new proof of Grünbaum's 3 color theorem, Star arboricity of graphs, On the minimal reducible bound for outerplanar and planar graphs, On acyclic colorings of graphs on surfaces, Acyclic coloring of claw-free graphs with small degree, Acyclic edge coloring of planar graphs without small cycles, Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11, Acyclic coloring of graphs without bichromatic long path, Maximum induced forests in graphs of bounded treewidth, Acyclic 4-choosability of planar graphs, An improved upper bound for the acyclic chromatic number of 1-planar graphs, Adapted game colouring of graphs, On low tree-depth decompositions, Improved bounds on linear coloring of plane graphs, Acyclic vertex coloring of graphs of maximum degree 5, Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph, Graphs with maximum degree \(6\) are acyclically \(11\)-colorable, \(k\)-forested coloring of planar graphs with large girth, The chromatic number of a signed graph, Planar graphs without 4- and 5-cycles are acyclically 4-choosable, From the plane to higher surfaces, Antisymmetric flows and strong oriented coloring of planar graphs, Frugal, acyclic and star colourings of graphs, On forbidden subdivision characterizations of graph classes, Nonrepetitive colorings of graphs -- a survey, Acyclic total colorings of planar graphs without \(l\) cycles, Acyclic 6-choosability of planar graphs without adjacent short cycles, Concepts of signed graph coloring, Degenerate and star colorings of graphs on surfaces, Restricted coloring problems on graphs with few \(P_4\)'s, Nonrepetitive colorings of line arrangements, An introduction to the discharging method via graph coloring, Nonrepetitive colouring via entropy compression, A better bound on the largest induced forests in triangle-free planar graph, On chromatic numbers of two extensions of planar graphs, Acyclically 3-colorable planar graphs, \(\mathcal Q\)-Ramsey classes of graphs, Acyclic colorings of locally planar graphs, Planar graphs without cycles of length from 4 to 7 are 3-colorable, A note on the acyclic 3-choosability of some planar graphs, Acyclic 3-choosability of sparse graphs with girth at least 7, What is on his mind?, Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles, Acyclic improper colouring of graphs with maximum degree 4, Acyclic 4-choosability of planar graphs without adjacent short cycles, On acyclic 4-choosability of planar graphs without short cycles, Circular vertex arboricity, Acyclic chromatic indices of planar graphs with large girth, Graph theory (algorithmic, algebraic, and metric problems), Lucky labelings of graphs, Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable, Acyclic \(L\)-coloring of graphs with maximum degrees 5 and 6, On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9, Acyclic edge coloring of subcubic graphs, Representing graphs as the intersection of cographs and threshold graphs, Acyclic 6-choosability of planar graphs without 5-cycles and adjacent 4-cycles, Coloring graphs without bichromatic cycles or paths, Acyclic and \(k\)-distance coloring of the grid, On the acyclic chromatic number of Hamming graphs, Each 3-polytope with minimum degree 5 has a 7-cycle with maximum degree at most 15, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Homomorphisms of edge-colored graphs and Coxeter groups, Decomposing a planar graph of girth 5 into an independent set and a forest, Star coloring outerplanar bipartite graphs, \(k\)-forested choosability of planar graphs and sparse graphs, On acyclically 4-colorable maximal planar graphs, Acyclic edge coloring of planar graphs with large girth, Acyclic coloring of graphs with maximum degree at most six, Acyclic edge colorings of planar graphs and series parallel graphs, Game colouring of the square of graphs, Linear coloring of planar graphs with large girth, Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles, Acyclic coloring of IC-planar graphs, Antisymmetric flows and strong colourings of oriented graphs, A bound for the game chromatic number of graphs, Surfaces, tree-width, clique-minors, and partitions, Colored homomorphisms of colored mixed graphs, The game coloring number of planar graphs, Minimum feedback vertex set and acyclic coloring., On vertex rankings of graphs and its relatives, Equitable partition of graphs into induced forests, The \(r\)-acyclic chromatic number of planar graphs, Complex and homomorphic chromatic number of signed planar simple graphs

Cites Work

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