Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
From MaRDI portal
Recommendations
Cited in
(56)- Dichotomy for bounded degree \(H\)-colouring
- Trees, paths, stars, caterpillars and spiders
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Independent feedback vertex set for P₅-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- (\(\Delta-k\))-critical graphs
- On the Grundy and b-chromatic numbers of a graph
- A construction of uniquely colourable graphs with equal colour class sizes
- Star colouring of bounded degree graphs and regular graphs
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Colouring \((P_r + P_s)\)-free graphs
- Colouring square-free graphs without long induced paths
- A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
- Open problems on graph coloring for special graph classes
- Function simulation, graph grammars and colourings
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- On the Grundy number of a graph
- scientific article; zbMATH DE number 6007698 (Why is no real title available?)
- Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
- DP-Complete Problems Derived from Extremal NP-Complete Properties
- First-fit colorings of graphs with no cycles of a prescribed even length
- Colouring square-free graphs without long induced paths
- Brooks' Theorem and Beyond
- scientific article; zbMATH DE number 4024813 (Why is no real title available?)
- The complexity of changing colourings with bounded maximum degree
- Colouring graphs when the number of colours is almost the maximum degree
- Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
- scientific article; zbMATH DE number 927067 (Why is no real title available?)
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- scientific article; zbMATH DE number 7378380 (Why is no real title available?)
- Distributed coloring of graphs with an optimal number of colors
- Colouring (P_r+P_s)-Free Graphs
- Colouring H-free graphs of bounded diameter.
- On graphs without a \(C_{4}\) or a diamond
- Uniquely circular colourable and uniquely fractional colourable graphs of large girth
- scientific article; zbMATH DE number 7651161 (Why is no real title available?)
- Colouring graphs of bounded diameter in the absence of small cycles
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Colouring graphs of bounded diameter in the absence of small cycles
- Bounds for the Grundy chromatic number of graphs in terms of domination number
- The complexity of star colouring in bounded degree graphs and regular graphs
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Hardness transitions and uniqueness of acyclic colouring
- On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
- Hardness transitions of star colouring and restricted star colouring
- Acyclic, star and injective colouring: a complexity picture for H-free graphs
- Inapproximability of counting hypergraph colourings
- Complexity of the list homomorphism problem in hereditary graph classes
- Minimal obstructions to C₅-Coloring in hereditary graph classes
- Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
- Minimal obstructions to C₅-coloring in hereditary graph classes
- Three-coloring triangle-free graphs without long forbidden paths
- \(H\)-coloring degree-bounded (acyclic) digraphs
This page was built for publication: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238167)
