Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
From MaRDI portal
Publication:4238167
DOI10.1017/S0963548398003678zbMath0918.05051OpenAlexW2099650681MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Star colouring of bounded degree graphs and regular graphs, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Trees, paths, stars, caterpillars and spiders, 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, Brooks' Theorem and Beyond, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Colouring square-free graphs without long induced paths., Colouring \((P_r + P_s)\)-free graphs, Bounds for the Grundy chromatic number of graphs in terms of domination number, The complexity of changing colourings with bounded maximum degree, 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, Unnamed Item, On the price of independence for vertex cover, feedback vertex set and odd cycle transversal, Unnamed Item, On the Grundy and \(b\)-chromatic numbers of a graph, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, 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, Independent feedback vertex set for \(P_5\)-free graphs, Classifying \(k\)-edge colouring for \(H\)-free graphs, A construction of uniquely colourable graphs with equal colour class sizes, On graphs without a \(C_{4}\) or a diamond, (\(\Delta-k\))-critical graphs, Unnamed Item, On the Grundy Number of a Graph, Dichotomy for bounded degree \(H\)-colouring, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of \((2P_4,C_5)\)-free graphs, \(H\)-coloring degree-bounded (acyclic) digraphs, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of \((2P_4,C_5)\)-free graphs, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Open Problems on Graph Coloring for Special Graph Classes, Colouring square-free graphs without long induced paths, Function simulation, graph grammars and colourings, A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
