Acyclic, star, and injective colouring: bounding the diameter
From MaRDI portal
Publication:5918693
DOI10.37236/10738zbMath1491.05074OpenAlexW3154573987WikidataQ114023887 ScholiaQ114023887MaRDI QIDQ5918693
Pascal Ochem, Petr A. Golovach, Siani Smith, Christoph Brause, Daniël Paulusma, Barnaby Martin
Publication date: 13 June 2022
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.37236/10738
Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (4)
Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Packings in bipartite prisms and hypercubes ⋮ The complexity of \(L(p, q)\)-edge-labelling
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- On the complexity of injective colorings and its generalizations
- Acyclic coloring with few division vertices
- The complexity of surjective homomorphism problems-a survey
- Restricted coloring problems on graphs with few \(P_4\)'s
- Acyclic and star colorings of cographs
- Complexity of restricted variant of star colouring
- On the maximum diameter of \(k\)-colorable graphs
- Star coloring high girth planar graphs
- The complexity of colouring problems on dense graphs
- The complexity of some problems related to GRAPH 3-COLORABILITY
- Algorithmic aspects of acyclic edge colorings
- On the computational complexity of strong edge coloring
- 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
- A polynomial time algorithm to find the star chromatic index of trees
- Partition the vertices of a graph into one independent set and one acyclic set
- Moore graphs and beyond: a survey of the degree/diameter problem
- Open Problems on Graph Coloring for Special Graph Classes
- Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
- Labelling Graphs with a Condition at Distance 2
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Approximations for -Colorings of Graphs
- Star chromatic index of subcubic multigraphs
- The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
- Colouring H-free graphs of bounded diameter.
- On Injective Colourings of Chordal Graphs
- Colouring graphs of bounded diameter in the absence of small cycles
- Acyclic, star, and injective colouring: bounding the diameter
This page was built for publication: Acyclic, star, and injective colouring: bounding the diameter
