scientific article; zbMATH DE number 2044943
From MaRDI portal
Publication:4448764
Recommendations
Cited in
(only showing first 100 items - show all)- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Towards an isomorphism dichotomy for hereditary graph classes
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- Non-empty intersection of longest paths in \(H\)-free graphs
- 3-colouring \(P_t\)-free graphs without short odd cycles
- Coloring graphs with forbidden induced subgraphs
- Algorithms for the rainbow vertex coloring problem on graph classes
- Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
- 3-colorable subclasses of \(P_8\)-free graphs
- Two cases of polynomial-time solvability for the coloring problem
- Polynomial cases for the vertex coloring problem
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- On coloring a class of claw-free and hole-twin-free graphs
- Revising Johnson's table for the 21st century
- Total domination, separated-cluster, CD-coloring: algorithms and hardness
- Graph clustering via generalized colorings
- Colouring of graphs with Ramsey-type forbidden subgraphs
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- Colouring of graphs with Ramsey-type forbidden subgraphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Vertex coloring of graphs with few obstructions
- Coloring graphs without short cycles and long induced paths
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Coloring graphs characterized by a forbidden subgraph
- Choosability of P 5-Free Graphs
- Colouring vertices of triangle-free graphs without forests
- Constructions of k-critical P₅-free graphs
- Colouring square-free graphs without long induced paths
- Complexity of total dominator coloring in graphs
- Bisimplicial separators
- The coloring problem for classes with two small obstructions
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Efficient approximation for restricted biclique cover problems
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
- Coloring graphs without short cycles and long induced paths
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- Independent feedback vertex set for \(P_5\)-free graphs
- Injective colouring for H-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Domination, coloring and stability in \(P_5\)-reducible graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Colouring H-free graphs of bounded diameter.
- Critical vertices and edges in \(H\)-free graphs
- Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs
- On Betti numbers of flag complexes with forbidden induced subgraphs
- Colouring of (P₃ P₂)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Reducing the chromatic number by vertex or edge deletions
- On the algorithmic aspects of strong subcoloring
- Graphs with at most two moplexes
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A coloring algorithm for \(4 K_1\)-free line graphs
- \((2P_2,K_4)\)-free graphs are 4-colorable
- Obstructions for three-coloring and list three-coloring \(H\)-free graphs
- Solving the clique cover problem on (bull, \(C_4\))-free graphs
- On coloring a class of claw-free graphs.
- A Note on k-Colorability of P 5-Free Graphs
- \textsc{max-cut} and containment relations in graphs
- Colouring \((P_r + P_s)\)-free graphs
- On the complexity of cd-coloring of graphs
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
- List k-colouring P_t-free graphs: a mim-width perspective
- List coloring in the absence of a linear forest
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Max-Cut and containment relations in graphs
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Colouring square-free graphs without long induced paths
- 3-colouring AT-free graphs in polynomial time
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- List coloring in the absence of a linear forest
- On line graphs of subcubic triangle-free graphs
- Boundary classes for graph problems involving non-local properties
- Colouring diamond-free graphs
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Colouring vertices of triangle-free graphs
- On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
- Open problems on graph coloring for special graph classes
- A complexity dichotomy and a new boundary class for the dominating set problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- scientific article; zbMATH DE number 1189243 (Why is no real title available?)
- Coloring graphs characterized by a forbidden subgraph
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Colouring (P_r+P_s)-Free Graphs
- On the complexity of colouring antiprismatic graphs
- List coloring in the absence of two subgraphs
- Partitioning \(H\)-free graphs of bounded diameter
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4448764)
