The complexity of colouring problems on dense graphs
From MaRDI portal
Publication:1079363
DOI10.1016/0304-3975(86)90184-2zbMath0597.68038OpenAlexW1968069760MaRDI QIDQ1079363
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90184-2
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15)
Related Items
4-Coloring H-Free Graphs When H Is Small, Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\), 4-colorability of \(P_6\)-free graphs, Partitioning \(H\)-free graphs of bounded diameter, Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, A randomised 3-colouring algorithm, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case, Colouring \((P_r + P_s)\)-free graphs, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph, Computing list homomorphisms in geometric intersection graphs, Complexity of \(C_k\)-coloring in hereditary classes of graphs, Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring, An approximation algorithm for 3-Colourability, 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring, List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\), Dominating set based exact algorithms for \(3\)-coloring, 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles, \(H\)-colorings of dense hypergraphs, 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs., List 3-coloring graphs with no induced \(P_6 + rP_3\), Independent feedback vertex set for \(P_5\)-free graphs, Solving problems on generalized convex graphs via mim-width, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Coloring bipartite hypergraphs, Unnamed Item, Approximately coloring graphs without long induced paths, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Efficiency in exponential time for domination-type problems, The sandwich problem for decompositions and almost monotone properties, Colouring graphs of bounded diameter in the absence of small cycles, Acyclic, star, and injective colouring: bounding the diameter, Colouring graphs of bounded diameter in the absence of small cycles, Acyclic, star, and injective colouring: bounding the diameter, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Updating the complexity status of coloring graphs without a fixed induced linear forest, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Faster 3-Coloring of Small-Diameter Graphs, Independent Feedback Vertex Set for P_5-free Graphs, Counting \(H-\)colorings of partial \(k-\)trees, Algorithms and almost tight results for 3-colorability of small diameter graphs
Cites Work
