Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
From MaRDI portal
Publication:4238167
DOI10.1017/S0963548398003678zbMath0918.05051MaRDI QIDQ4238167
Thomas Emden-Weinert, Stefan Hougardy, Bernd Kreuter
Publication date: 13 April 1999
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548398003678
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
Related Items
Unnamed Item, Unnamed Item, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Unnamed Item, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of \((2P_4,C_5)\)-free graphs, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of \((2P_4,C_5)\)-free graphs, 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, First-fit colorings of graphs with no cycles of a prescribed even length, 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, On graphs without a \(C_{4}\) or a diamond, \(H\)-coloring degree-bounded (acyclic) digraphs, 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_5\)-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, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, DP-Complete Problems Derived from Extremal NP-Complete Properties, Brooks' Theorem and Beyond, Colouring square-free graphs without long induced paths.
