The 3-Colorability Problem on Graphs with Maximum Degree Four
From MaRDI portal
Publication:4429678
DOI10.1137/S0097539702418759zbMath1026.05040OpenAlexW2086843521MaRDI QIDQ4429678
Martin Kochol, Bert Randerath, Vadim V. Lozin
Publication date: 28 September 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702418759
Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (15)
Solving Problems on Graphs of High Rank-Width ⋮ Vertex coloring of graphs with few obstructions ⋮ On the number of boundary classes in the 3-colouring problem ⋮ Brooks' theorem for generalized dart graphs ⋮ Three colorability characterized by shrinking of locally connected subgraphs into triangles ⋮ Solving problems on graphs of high rank-width ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ The coloring problem for classes with two small obstructions ⋮ Dichotomy for Coloring of Dart Graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Coloring vertices of claw-free graphs in three colors ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Colouring vertices of triangle-free graphs without forests ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
This page was built for publication: The 3-Colorability Problem on Graphs with Maximum Degree Four
