Acyclic, star, and injective colouring: bounding the diameter
From MaRDI portal
Publication:5925554
DOI10.1007/978-3-030-86838-3_26OpenAlexW3197816290MaRDI QIDQ5925554
Christoph Brause, Siani Smith, Daniël Paulusma, Petr A. Golovach, Barnaby Martin
Publication date: 8 June 2022
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2104.10593
Related Items (5)
The complexity of \(L(p, q)\)-edge-labelling ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Faster 3-Coloring of Small-Diameter Graphs
Cites Work
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- On the complexity of injective colorings and its generalizations
- The complexity of surjective homomorphism problems-a survey
- Complexity of restricted variant of star colouring
- The complexity of colouring problems on dense graphs
- Independent feedback vertex sets for graphs of bounded diameter
- Star coloring of certain graph classes
- On the injective chromatic number of graphs
- Coloring with no 2-colored \(P_4\)'s
- Three complexity results on coloring \(P_k\)-free graphs
- Injective colouring for H-free graphs
- Partition the vertices of a graph into one independent set and one acyclic set
- Open Problems on Graph Coloring for Special Graph Classes
- Labelling Graphs with a Condition at Distance 2
- Approximations for -Colorings of Graphs
- Colouring H-free graphs of bounded diameter.
- On Injective Colourings of Chordal Graphs
- Colouring graphs of bounded diameter in the absence of small cycles
This page was built for publication: Acyclic, star, and injective colouring: bounding the diameter
