Acyclic coloring of graphs
From MaRDI portal
A proper vertex colouring (adjacent vertices have distinct colours) of a finite simple undirected graph \(G\) is acyclic if there is no cycle in \(G\) induced by the vertices of any two of the colours. The acyclic chromatic number \(A(G)\) of \(G\) is the least number of colours in an acyclic colouring of \(G\). The main result \[ A(G)=O(d^{4/3}) \hbox{ as } d\to \infty \] for every graph \(G\) of maximum degree \(d\) settles a problem of Erdős. All proofs rely heavily on probabilistic arguments.
Recommendations
Cites work
Cited in
(only showing first 100 items - show all)- Acyclic and \(k\)-distance coloring of the grid
- On the acyclic chromatic number of Hamming graphs
- Acyclic edge coloring of planar graphs with large girth
- Acyclic edge colorings of planar graphs and series parallel graphs
- Probabilistic methods in coloring and decomposition problems
- Acyclic edge-colorings of sparse graphs
- Linear coloring of graphs
- Improved upper bound for generalized acyclic chromatic number of graphs
- Acyclic edge coloring of 4-regular graphs without 3-cycles
- Generalized acyclic edge colorings via entropy compression
- \(\mathcal Q\)-Ramsey classes of graphs
- Searching for acyclic orientations of graphs
- On acyclic colorings of graphs on surfaces
- Acyclic colorings of graph subdivisions revisited
- Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices
- On acyclic edge coloring of toroidal graphs
- Graphs with maximum degree 6 are acyclically 11-colorable
- Acyclic edge coloring of planar graphs without 4-cycles
- Efficient algorithms for acyclic colorings of graphs
- Entropy compression versus Lovász local lemma
- Acyclic edge coloring of IC-planar graphs
- Coloring graphs without bichromatic cycles or paths
- Turán density of 2-edge-colored bipartite graphs with application on \(\{2, 3\}\)-hypergraphs
- Acyclic edge coloring of chordal graphs with bounded degree
- Acyclic choosability of graphs with bounded degree
- Approximations of acyclic graphs
- Acyclic coloring of claw-free graphs with small degree
- Edge-coloring of plane multigraphs with many colors on facial cycles
- A new bound on the acyclic edge chromatic number
- Intersection dimension and graph invariants
- Acyclic sum-list-colouring of cylinders
- Acyclic edge coloring of planar graphs without cycles of specific lengths
- Acyclic edge coloring of 4-regular graphs. II.
- Acyclic chromatic indices of planar graphs with large girth
- Acyclic \(L\)-coloring of graphs with maximum degrees 5 and 6
- Acyclic coloring of graphs and entropy compression method
- Measurable versions of the Lovász local lemma and measurable graph colorings
- Acyclic coloring of graphs with maximum degree at most six
- The \(r\)-acyclic chromatic number of planar graphs
- The local cut lemma
- Acyclic coloring of graphs of maximum degree five: nine colors are enough
- Acyclic chromatic index of triangle-free 1-planar graphs
- The method of coloring in graphs and its application
- Acyclic edge coloring of graphs
- The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle
- Acyclic edge-coloring using entropy compression
- Acyclic edge coloring of planar graphs without adjacent cycles
- Acyclic vertex coloring of graphs of maximum degree six
- Improved bounds on acyclic edge colouring
- Tree-depth, subgraph coloring and homomorphism bounds
- Bounds on the generalised acyclic chromatic numbers of bounded degree graphs
- Acyclic coloring of graphs with maximum degree 7
- On b-acyclic chromatic number of a graph
- Improved bounds on the generalized acyclic chromatic number
- Acyclic edge colorings of graphs
- Acyclic coloring of graphs with some girth restriction
- Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
- Acyclic vertex coloring of graphs of maximum degree six
- Acyclic colouring of some line graphs
- New bounds for the acyclic chromatic index
- A survey of graph coloring -- its types, methods and applications
- An algorithm for optimal acyclic edge-colouring of cubic graphs
- Bounds on vertex colorings with restrictions on the union of color classes
- Planarization and acyclic colorings of subcubic claw-free graphs
- Acyclic edge coloring of 2-degenerate graphs
- Polychromatic Acyclic Tours in Colored Multigraphs
- Two lower bounds for p-centered colorings
- A Conjecture of Borodin and a Coloring of Grünbaum
- A note on acyclic vertex-colorings
- scientific article; zbMATH DE number 6511307 (Why is no real title available?)
- On acyclic colorings of direct produts
- Acyclic edge coloring of graphs with maximum degree 4
- Graph colorings and acyclic orientations
- Acyclic coloring with few division vertices
- Upper bounds for harmonious colorings
- scientific article; zbMATH DE number 95655 (Why is no real title available?)
- Improved upper bounds on acyclic edge colorings
- Some results on acyclic edge coloring of plane graphs
- Improved bounds on coloring of graphs
- Acyclic edge coloring of planar graphs without 5-cycles
- Acyclic edge colouring of plane graphs
- Acyclic chromatic indices of planar graphs with girth at least five
- Acyclic chromatic indices of fully subdivided graphs
- On \(r\)-acyclic edge colorings of planar graphs
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- On the adjacent vertex-distinguishing acyclic edge coloring of some graphs
- Randomly colouring graphs (a combinatorial view)
- Acyclic edge-coloring of planar graphs: \(\Delta\) colors suffice when \(\Delta\) is large
- Acyclic sum-list-colouring of grids and other classes of graphs
- Acyclic total colorings of planar graphs without \(l\) cycles
- Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle
- Star Chromatic Index
- Acyclic edge colourings of graphs with large girth
- Acyclic list edge coloring of graphs with maximum degree 4
- d‐Regular graphs of acyclic chromatic index at least d+2
- Coloring parameters for graphs on surfaces
- Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4
- Improved bounds for acyclic chromatic index of planar graphs
- scientific article; zbMATH DE number 7651161 (Why is no real title available?)
- A polyhedral study of the acyclic coloring problem
This page was built for publication: Acyclic coloring of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3977081)
