scientific article; zbMATH DE number 772747
From MaRDI portal
Publication:4838453
zbMath0821.05027MaRDI QIDQ4838453
Publication date: 12 July 1995
Full work available at URL: https://eudml.org/doc/118661
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (32)
Algorithmic complexity of list colorings ⋮ Coloring problems on bipartite graphs of small diameter ⋮ The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ Coloring some classes of mixed graphs ⋮ Generalized coloring for tree-like graphs ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete ⋮ Data reduction for graph coloring problems ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ On the complexity of coloring ‐graphs ⋮ On the complexity of restoring corrupted colorings ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Fixing improper colorings of graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Approximation algorithms for time constrained scheduling ⋮ List coloring in the absence of a linear forest ⋮ Unnamed Item ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Unnamed Item ⋮ Data Reduction for Graph Coloring Problems ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ List edge multicoloring in graphs with few cycles ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ List Coloring in the Absence of a Linear Forest
This page was built for publication:
