scientific article; zbMATH DE number 7651161
From MaRDI portal
Publication:5874489
DOI10.4230/LIPIcs.ESA.2020.22MaRDI QIDQ5874489
Jan Bok, Siani Smith, Nikola Jedličková, Barnaby Martin, Daniël Paulusma
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2008.09415
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (6)
Star colouring of bounded degree graphs and regular graphs ⋮ The complexity of star colouring in bounded degree graphs and regular graphs ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Injective colouring for H-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Acyclically 4-colorable triangulations
- On the complexity of injective colorings and its generalizations
- Acyclic coloring with few division vertices
- Distance three labelings of trees
- Restricted coloring problems on graphs with few \(P_4\)'s
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Frugal, acyclic and star colourings of graphs
- Acyclic and star colorings of cographs
- Acyclically 3-colorable planar graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Paw-free graphs
- On acyclic colorings of planar graphs
- Algorithmic aspects of acyclic edge colorings
- The four-colour theorem
- On the computational complexity of strong edge coloring
- Star coloring of certain graph classes
- Independent feedback vertex set for \(P_5\)-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- On the injective chromatic number of graphs
- Minimum feedback vertex set and acyclic coloring.
- Coloring with no 2-colored \(P_4\)'s
- Disjoint triangles of a cubic line graph
- Acyclic coloring of graphs of maximum degree five: nine colors are enough
- Coloring graphs without short cycles and long induced paths
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- Star coloring of graphs
- Graph Theory and Probability
- The NP-Completeness of Edge-Coloring
- Acyclic coloring of graphs
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Approximations for -Colorings of Graphs
- Star chromatic index of subcubic multigraphs
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- NP completeness of finding the chromatic index of regular graphs
- Star Chromatic Index
- Colouring (P_r+P_s)-Free Graphs
- On Injective Colourings of Chordal Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Fixed-parameter complexity of \(\lambda\)-labelings
This page was built for publication:
