Pages that link to "Item:Q1356685"
From MaRDI portal
The following pages link to On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs (Q1356685):
Displaying 50 items.
- Algorithms and almost tight results for 3-colorability of small diameter graphs (Q261372) (← links)
- First-fit colorings of graphs with no cycles of a prescribed even length (Q326475) (← links)
- Vertex coloring of graphs with few obstructions (Q344868) (← links)
- Colouring of graphs with Ramsey-type forbidden subgraphs (Q393895) (← links)
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane (Q412277) (← links)
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time (Q417995) (← links)
- On the parameterized complexity of coloring graphs in the absence of a linear forest (Q450579) (← links)
- Coloring graphs characterized by a forbidden subgraph (Q476308) (← links)
- The coloring problem for classes with two small obstructions (Q479257) (← links)
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs (Q521809) (← links)
- A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length (Q528481) (← links)
- Covering line graphs with equivalence relations (Q608272) (← links)
- Polynomial cases for the vertex coloring problem (Q666663) (← links)
- \(K_3\)-WORM colorings of graphs: lower chromatic number and gaps in the chromatic spectrum (Q726653) (← links)
- Colouring vertices of triangle-free graphs without forests (Q764907) (← links)
- The structure of bull-free graphs I -- three-edge-paths with centers and anticenters (Q765202) (← links)
- NP-hardness of the recognition of coordinated graphs (Q839773) (← links)
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time (Q848637) (← links)
- Exact complexity of exact-four-colorability (Q1014384) (← links)
- Trahtenbrot-Zykov problem and NP-completeness (Q1201257) (← links)
- The complexity of some problems related to GRAPH 3-COLORABILITY (Q1281385) (← links)
- The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3 (Q1354146) (← links)
- Coloring the hypergraph of maximal cliques of a graph with no long path (Q1412673) (← links)
- 3-colorability and forbidden subgraphs. I: Characterizing pairs (Q1422435) (← links)
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. (Q1427186) (← links)
- The NP-completeness of (1,r)-subcolorability of cubic graphs (Q1603517) (← links)
- Trees, paths, stars, caterpillars and spiders (Q1635718) (← links)
- Some problems on induced subgraphs (Q1693168) (← links)
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs (Q1707976) (← links)
- Three colorability characterized by shrinking of locally connected subgraphs into triangles (Q1708265) (← links)
- On the complexity of graph coloring with additional local conditions (Q1708276) (← links)
- Critical vertices and edges in \(H\)-free graphs (Q1730263) (← links)
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices (Q1786047) (← links)
- Greedy algorithms for triangle free coloring (Q1927697) (← links)
- On 3-colouring of graphs with short faces and bounded maximum vertex degree (Q2030141) (← links)
- Revising Johnson's table for the 21st century (Q2091799) (← links)
- Induced star partition of graphs (Q2161236) (← links)
- On some graph classes related to perfect graphs: a survey (Q2184662) (← links)
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path (Q2216431) (← links)
- On the tractability of \(( k , i )\)-coloring (Q2235289) (← links)
- Coloring vertices of claw-free graphs in three colors (Q2251141) (← links)
- List coloring in the absence of a linear forest (Q2258070) (← links)
- Domination, coloring and stability in \(P_5\)-reducible graphs (Q2341757) (← links)
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs (Q2352049) (← links)
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs (Q2409536) (← links)
- Coloring graphs without short cycles and long induced paths (Q2440105) (← links)
- NP-hard graph problems and boundary classes of graphs (Q2465640) (← links)
- Partition the vertices of a graph into one independent set and one acyclic set (Q2497500) (← links)
- Vertex elimination orderings for hereditary graph classes (Q2514166) (← links)
- List coloring in the absence of two subgraphs (Q2636800) (← links)
