Hardness transitions and uniqueness of acyclic colouring
From MaRDI portal
Publication:6145810
DOI10.1016/j.dam.2023.11.030zbMath1530.05055arXiv2309.11212MaRDI QIDQ6145810
Publication date: 9 January 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2309.11212
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Acyclic coloring of graphs with some girth restriction
- A note on acyclic vertex-colorings
- Acyclic coloring with few division vertices
- Improved bounds on coloring of graphs
- Colouring graphs when the number of colours is almost the maximum degree
- Restricted coloring problems on graphs with few \(P_4\)'s
- Acyclic and star colorings of cographs
- Acyclically 3-colorable planar graphs
- Acyclic 3-choosability of sparse graphs with girth at least 7
- Acyclic colorings of subcubic graphs
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Acyclic and \(k\)-distance coloring of the grid
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- On acyclic colorings of planar graphs
- Algorithmic aspects of acyclic edge colorings
- Disjoint triangles of a cubic line graph
- On acyclic colorings of graphs on surfaces
- Colorings of plane graphs: a survey
- Entropy compression versus Lovász local lemma
- Acyclic edge coloring of chordal graphs with bounded degree
- Injective colouring for H-free graphs
- Star colouring of bounded degree graphs and regular graphs
- Acyclic coloring of claw-free graphs with small degree
- An improved upper bound for the acyclic chromatic number of 1-planar graphs
- Acyclic coloring of graphs and entropy compression method
- On vertex rankings of graphs and its relatives
- Acyclic edge coloring of graphs
- Improved bounds on acyclic edge colouring
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Popular matchings in complete graphs
- Open Problems on Graph Coloring for Special Graph Classes
- Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
- Star Coloring and Acyclic Coloring of Locally Planar Graphs
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- Acyclic edge coloring of 2-degenerate graphs
- Graphs with maximum degree 5 are acyclically 7-colorable
- New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
- Acyclic coloring of graphs
- On the Structure of Polynomial Time Reducibility
- An acyclic analogue to Heawood's theorem
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Kernelization
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- NP completeness of finding the chromatic index of regular graphs
- Computational Complexity
- What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
- Acyclic, star, and injective colouring: bounding the diameter
- Acyclic colorings of planar graphs
- Acyclic colouring of 1-planar graphs
- Acyclic 3-coloring of generalized Petersen graphs
This page was built for publication: Hardness transitions and uniqueness of acyclic colouring
