The Proper Interval Colored Graph problem for caterpillar trees
From MaRDI portal
Publication:3439122
DOI10.1016/j.endm.2004.03.008zbMath1152.05325MaRDI QIDQ3439122
Publication date: 29 May 2007
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2004.03.008
05C15: Coloring of graphs and hypergraphs
Related Items
An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, A Quartic Kernel for Pathwidth-One Vertex Deletion, An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of DNA physical mapping
- Beyond NP-completeness for problems of bounded width (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- The Profile Minimization Problem in Trees
- Graph Sandwich Problems
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- The hardness of intervalizing four colored caterpillars