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 32 items.
- 3-colouring \(P_t\)-free graphs without short odd cycles (Q2696271) (← links)
- 3-colorability of pseudo-triangulations (Q2792798) (← links)
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions (Q2835660) (← links)
- On generating triangle-free graphs (Q2839211) (← links)
- 4-Coloring H-Free Graphs When H Is Small (Q2891376) (← links)
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (Q2978179) (← links)
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete (Q3029023) (← links)
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs (Q3057613) (← links)
- Colouring Vertices of Triangle-Free Graphs (Q3057624) (← links)
- Coloring Graphs without Short Cycles and Long Induced Paths (Q3088283) (← links)
- List Coloring in the Absence of a Linear Forest (Q3104770) (← links)
- Trees, Paths, Stars, Caterpillars and Spiders (Q3467870) (← links)
- (Q4370210) (← links)
- Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete (Q4378523) (← links)
- Independent sets in asteroidal triple-free graphs (Q4572004) (← links)
- 3-colorability of 4-regular hamiltonian graphs (Q4797925) (← links)
- A Class of Three‐Colorable Triangle‐Free Graphs (Q4916101) (← links)
- Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ (Q4982280) (← links)
- A structure theorem for graphs with no cycle with a unique chord and its consequences (Q5189239) (← links)
- On the complexity for constructing a 3-colouring for planar graphs with short facets (Q5213298) (← links)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs (Q5900083) (← links)
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs (Q5900860) (← links)
- Between 2- and 3-colorability (Q5902303) (← links)
- Complexity of fall coloring for restricted graph classes (Q5918283) (← links)
- Two cases of polynomial-time solvability for the coloring problem (Q5963654) (← links)
- A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs (Q6039897) (← links)
- Minimum weighted clique cover on claw‐free perfect graphs (Q6055392) (← links)
- Star covers and star partitions of double-split graphs (Q6124494) (← links)
- Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs (Q6180578) (← links)
- On star partition of split graphs (Q6547833) (← links)
- Star covers and star partitions of cographs and butterfly-free graphs (Q6547835) (← links)
- Discrete preference games with logic-based agents: formal framework, complexity, and islands of tractability (Q6579293) (← links)
