Coloring edges and vertices of graphs without short or long cycles

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
Coloring graphs without short cycles and long induced paths
On 3-colouring of graphs with short faces and bounded maximum vertex degree
Some results concerning the complexity of restricted colorings of graphs
On the NP-completeness of the $k$-colorability problem for triangle-free graphs

Cited in

(62)

On the parameterized complexity of coloring graphs in the absence of a linear forest
Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
$H$-colouring $P_t$-free graphs in subexponential time
Better 3-coloring algorithms: excluding a triangle and a seven vertex path
Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four
Coloring vertices of claw-free graphs in three colors
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
Colouring vertices of triangle-free graphs without forests
The coloring problem for classes with two small obstructions
scientific article; zbMATH DE number 7525468 (Why is no real title available?)
Coloring graphs without short cycles and long induced paths
Pushing vertices in digraphs without long induced cycles
Independent feedback vertex set for $P_5$-free graphs
Updating the complexity status of coloring graphs without a fixed induced linear forest
scientific article; zbMATH DE number 7656024 (Why is no real title available?)
Strong cliques in diamond-free graphs
A refinement on the structure of vertex-critical $(P_5, \mathrm{gem})$-free graphs
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Graphs with girth at least 8 are b-continuous
Certifying coloring algorithms for graphs without long induced paths
Complexity of $C_k$-coloring in hereditary classes of graphs
scientific article; zbMATH DE number 4075110 (Why is no real title available?)
The induced separation dimension of a graph
Obstructions for three-coloring and list three-coloring $H$-free graphs
List coloring in the absence of a linear forest
Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
List coloring in the absence of a linear forest
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
Parameterized and exact algorithms for class domination coloring
4-colorability of P₆-free graphs
Parameterized and exact algorithms for class domination coloring
On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
Colouring graphs of bounded diameter in the absence of small cycles
Colouring graphs of bounded diameter in the absence of small cycles
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
Boundary properties of the satisfiability problems
Complexity classification of the edge coloring problem for a family of graph classes
Complexity of coloring graphs without paths and cycles
A decidability result for the dominating set problem
Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
Connected greedy coloring of H-free graphs
Graphs vertex-partitionable into strong cliques
Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
The $b$-continuity of graphs with large girth
4-coloring $H$-free graphs when $H$ is small
List-3-coloring ordered graphs with a forbidden induced subgraphs
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
scientific article; zbMATH DE number 7651161 (Why is no real title available?)
Improved complexity results on $k$-coloring $P_t$-free graphs
$b$-continuity and partial Grundy coloring of graphs with large girth
3-colouring $P_t$-free graphs without short odd cycles
Graphs with large girth are $b$-continuous
3-colorable subclasses of $P_8$-free graphs
Infinite families of $k$-vertex-critical $(P_5, C_5)$-free graphs
Vertex-critical $( P_3 + \ell P_1 )$-free and vertex-critical (gem, co-gem)-free graphs
A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length

This page was built for publication: Coloring edges and vertices of graphs without short or long cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558598)