On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
From MaRDI portal
Publication:1356685
DOI10.1016/S0012-365X(97)89267-9zbMath0870.05021OpenAlexW2068121436MaRDI QIDQ1356685
Frédéric Maffray, Myriam Preissmann
Publication date: 10 June 1997
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0012-365x(97)89267-9
Related Items (62)
4-Coloring H-Free Graphs When H Is Small ⋮ NP-hardness of the recognition of coordinated graphs ⋮ Trees, paths, stars, caterpillars and spiders ⋮ List coloring in the absence of two subgraphs ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ First-fit colorings of graphs with no cycles of a prescribed even length ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ Vertex coloring of graphs with few obstructions ⋮ Induced star partition of graphs ⋮ Independent sets in asteroidal triple-free graphs ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ Covering line graphs with equivalence relations ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Some problems on induced subgraphs ⋮ Star covers and star partitions of double-split graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ Coloring the hypergraph of maximal cliques of a graph with no long path ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Three colorability characterized by shrinking of locally connected subgraphs into triangles ⋮ Coloring graphs without short cycles and long induced paths ⋮ 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 ⋮ 3-colorability and forbidden subgraphs. I: Characterizing pairs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ The coloring problem for classes with two small obstructions ⋮ Polynomial cases for the vertex coloring problem ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Coloring vertices of claw-free graphs in three colors ⋮ A Class of Three‐Colorable Triangle‐Free Graphs ⋮ List coloring in the absence of a linear forest ⋮ Partition the vertices of a graph into one independent set and one acyclic set ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ \(K_3\)-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Complexity of fall coloring for restricted graph classes ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Colouring vertices of triangle-free graphs without forests ⋮ The structure of bull-free graphs I -- three-edge-paths with centers and anticenters ⋮ The complexity of some problems related to GRAPH 3-COLORABILITY ⋮ List Coloring in the Absence of a Linear Forest ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Revising Johnson's table for the 21st century ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ The NP-completeness of (1,r)-subcolorability of cubic graphs ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs
Cites Work
This page was built for publication: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
