scientific article
From MaRDI portal
Publication:3558598
zbMath1188.05065MaRDI QIDQ3558598
Marcin Kaminski, Vadim V. Lozin
Publication date: 5 May 2010
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (57)
4-Coloring H-Free Graphs When H Is Small ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Graphs with girth at least 8 are b-continuous ⋮ Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs ⋮ 4-colorability of \(P_6\)-free graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ Vertex coloring of graphs with few obstructions ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ \(b\)-continuity and partial Grundy coloring of graphs with large girth ⋮ The \(b\)-continuity of graphs with large girth ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ A decidability result for the dominating set problem ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Unnamed Item ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Unnamed Item ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Graphs vertex-partitionable into strong cliques ⋮ Coloring graphs without short cycles and long induced paths ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Boundary properties of the satisfiability problems ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ The coloring problem for classes with two small obstructions ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ 3-Colorable Subclasses of $P_8$-Free Graphs ⋮ Graphs with large girth are \(b\)-continuous ⋮ Coloring vertices of claw-free graphs in three colors ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Unnamed Item ⋮ Approximately coloring graphs without long induced paths ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ The induced separation dimension of a graph ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ Strong cliques in diamond-free graphs ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ List Coloring in the Absence of a Linear Forest ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
This page was built for publication:
