Open Problems on Graph Coloring for Special Graph Classes
From MaRDI portal
Publication:2827799
DOI10.1007/978-3-662-53174-7_2zbMath1417.05077OpenAlexW2501984361MaRDI QIDQ2827799
Publication date: 21 October 2016
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/16186/1/16186.pdf
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (17)
Coloring problems on bipartite graphs of small diameter ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ List-coloring -- parameterizing from triviality ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Fixed-parameter tractability of \((n-k)\) list coloring ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Colouring H-free graphs of bounded diameter. ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring graphs when the number of colours is almost the maximum degree
- An on-line competitive algorithm for coloring bipartite graphs without long induced paths
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- On the complexity of some colorful problems parameterized by treewidth
- Parameterized coloring problems on chordal graphs
- The strong perfect graph theorem
- Chordal deletion is fixed-parameter tractable
- On the complexity of H-coloring
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Effective on-line coloring of \(P_ 5\)-free graphs
- Some simplified NP-complete graph problems
- On-line coloring \(k\)-colorable graphs
- Algorithmic complexity of list colorings
- Generalized coloring for tree-like graphs
- Parameterized complexity of vertex colouring
- Edge dominating set and colorings on graphs with fixed clique-width
- Vertex colouring and forbidden subgraphs -- a survey
- 3-colouring AT-free graphs in polynomial time
- On some coloring problems in grids
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Precoloring extension on unit interval graphs
- Approximating clique-width and branch-width
- Hard coloring problems in low degree planar bipartite graphs
- List coloring in the absence of two subgraphs
- Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Colouring AT-Free Graphs
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Data Reduction for Graph Coloring Problems
- Vertex Coloring of Comparability+ke and –ke Graphs
- A New Algorithm for On-line Coloring Bipartite Graphs
- Interval Completion Is Fixed Parameter Tractable
- On-line and first fit colorings of graphs
- The Linearity of First-Fit Coloring of Interval Graphs
- Every Planar Map is Four Colorable
- Graph colorings with local constraints -- a survey
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Independent Sets in Asteroidal Triple-Free Graphs
- On-Line Coloring and Recursive Graph Theory
- Precoloring Extension III: Classes of Perfect Graphs
- Even-hole-free graphs: A survey
- Coloring Graphs with Constraints on Connectivity
- On List Coloring and List Homomorphism of Permutation and Interval Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Parameterized and Exact Computation
- On the Relationship Between Clique-Width and Treewidth
- On-line coloring between two lines
- Exploring the complexity boundary between coloring and list-coloring
This page was built for publication: Open Problems on Graph Coloring for Special Graph Classes
