A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (Q2978179)

scientific article

Language	Label	Description	Also known as
English	A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs	scientific article

Statements

instance of

scholarly article

0 references

title

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (English)

0 references

0 references

0 references

0 references

0 references

Journal of Graph Theory

0 references

publication date

21 April 2017

0 references

full work available at URL

https://arxiv.org/abs/1407.1482

0 references

http://dro.dur.ac.uk/18074/1/18074.pdf

0 references

zbMATH Keywords

graph coloring

0 references

precoloring extension

0 references

list coloring

0 references

choosability

0 references

forbidden induced subgraph

0 references

describes a project that uses

CriticalPfreeGraphs

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3142409

0 references

Every Planar Map is Four Colorable

0 references

On graphs with polynomially solvable maximum-weight clique problem

0 references

Three-coloring and list three-coloring of graphs without induced paths on seven vertices

0 references

Exploring the complexity boundary between coloring and list-coloring

0 references

Bounding the Clique-Width of H-free Chordal Graphs

0 references

On the structure of ($P_{5}$,\,gem)-free graphs

0 references

GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH

0 references

Triangle-free graphs and forbidden subgraphs

0 references

Three complexity results on coloring $P_k$-free graphs

0 references

Determining the chromatic number of triangle-free $2P_3$-free graphs in polynomial time

0 references

Updating the complexity status of coloring graphs without a fixed induced linear forest

0 references

A Certifying Algorithm for 3-Colorability of P 5-Free Graphs

0 references

4‐Coloring <i>P</i> <sub>6</sub> ‐Free Graphs with No Induced 5‐Cycles

0 references

Upper bounds to the clique width of graphs

0 references

On the parameterized complexity of coloring graphs in the absence of a linear forest

0 references

List coloring in the absence of a linear forest

0 references

Colouring of graphs with Ramsey-type forbidden subgraphs

0 references

Bounding Clique-Width via Perfect Graphs

0 references

Colouring vertices of triangle-free graphs without forests

0 references

Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs

0 references

Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

0 references

List-coloring claw-free graphs with small clique number

0 references

The chromatic number of $\{P_5,K_4\}$-free graphs

0 references

Forbidden Subgraphs and 3-Colorings

0 references

Maximum-Minimum Sätze über Graphen

0 references

The list chromatic index of a bipartite multigraph

0 references

Some simplified NP-complete graph problems

0 references

Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs

0 references

Choosability on $H$-free graphs

0 references

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

0 references

4-coloring $H$-free graphs when $H$ is small

0 references

List coloring in the absence of two subgraphs

0 references

Coloring graphs without short cycles and long induced paths

0 references

Closing complexity gaps for coloring problems on $H$-free graphs

0 references

ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

0 references

Coloring the hypergraph of maximal cliques of a graph with no long path

0 references

The complexity of planar graph choosability

0 references

Some results on $(a:b)$-choosability

0 references

Induced subtrees in graphs of large chromatic number

0 references

Some upper bounds on the total and list chromatic numbers of multigraphs

0 references

Complexity of coloring graphs without paths and cycles

0 references

Deciding $k$-colorability of $P_5$-free graphs in polynomial time

0 references

Polynomial-time algorithms for minimum weighted colorings of $(P_5, \overline{P}_5)$-free graphs and similar graph classes

0 references

A Characterization of b-Perfect Graphs

0 references

Constructions of $k$-critical $P_5$-free graphs

0 references

The NP-Completeness of Edge-Coloring

0 references

Improved complexity results on $k$-coloring $P_t$-free graphs

0 references

Q4838466

0 references

Precoloring Extension III: Classes of Perfect Graphs

0 references

Generalized coloring for tree-like graphs

0 references

Q5755526

0 references

Edge dominating set and colorings on graphs with fixed clique-width

0 references

Q4838453

0 references

On the complexity of 4-coloring graphs without long induced paths

0 references

NP completeness of finding the chromatic index of regular graphs

0 references

Vertex coloring of graphs with few obstructions

0 references

Coloring vertices of claw-free graphs in three colors

0 references

Some results on graphs without long induced paths

0 references

On $3$-Colorable $P_5$-Free Graphs

0 references

On the NP-completeness of the $k$-colorability problem for triangle-free graphs

0 references

The coloring problem for classes with two small obstructions

0 references

The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

0 references

Two cases of polynomial-time solvability for the coloring problem

0 references

Certifying algorithms

0 references

Q5710169

0 references

Paw-free graphs

0 references

Graph-Theoretic Concepts in Computer Science

0 references

Triangle-free $2P_3$-free graphs are 4-colorable

0 references

3-colorability and forbidden subgraphs. I: Characterizing pairs

0 references

Q4780499

0 references

3-colorability $\in \mathcal P$ for $P_{6}$-free graphs.

0 references

Vertex colouring and forbidden subgraphs -- a survey

0 references

Three-colourability and forbidden subgraphs. II: Polynomial algorithms

0 references

Some new hereditary classes where graph coloring remains NP-hard

0 references

A New Algorithm for Generating All the Maximal Independent Sets

0 references

Graph colorings with local constraints -- a survey

0 references

A bound on the chromatic number of graphs without certain induced subgraphs

0 references

Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree

0 references

Q2770587

0 references

Identifiers

zbMATH Open document ID

1359.05039

0 references

DOI

10.1002/jgt.22028

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2978179