Generalized coloring for tree-like graphs
From MaRDI portal
Publication:1363645
DOI10.1016/S0166-218X(96)00085-6zbMATH Open0879.68076OpenAlexW2088330156MaRDI QIDQ1363645FDOQ1363645
Publication date: 10 August 1997
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Recommendations
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Complement reducible graphs
- Title not available (Why is that?)
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graph minors. II. Algorithmic aspects of tree-width
- A linear time algorithm for finding tree-decompositions of small treewidth
- A Linear Recognition Algorithm for Cographs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Precoloring extension. I: Interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear-time computation of optimal subgraphs of decomposable graphs
- Title not available (Why is that?)
Cited In (49)
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- Slightly Superexponential Parameterized Problems
- On the complexity of coloring ‐graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Coloring problems on bipartite graphs of small diameter
- On coloring problems with local constraints
- Hard coloring problems in low degree planar bipartite graphs
- Exploring the complexity boundary between coloring and list-coloring
- Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
- Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints
- Coloring graphs without short cycles and long induced paths
- Using local search to speed up filtering algorithms for some NP-hard constraints
- Incremental list coloring of graphs, parameterized by conservation
- Combinatorial problems on \(H\)-graphs
- All subgraphs of a wheel are 5-coupled-choosable
- On \(H\)-topological intersection graphs
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
- Acyclic and star colorings of cographs
- Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
- On list \(k\)-coloring convex bipartite graphs
- Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
- On algorithms for (\(P_5\), gem)-free graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Clique‐width: Harnessing the power of atoms
- Exploring the complexity boundary between coloring and list-coloring
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Building graphs from colored trees
- Time slot scheduling of compatible jobs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Data reduction for graph coloring problems
- Complexity of list coloring problems with a fixed total number of colors
- List coloring in the absence of two subgraphs
- Counting \(H-\)colorings of partial \(k-\)trees
- List Coloring in the Absence of a Linear Forest
- Parameterized complexity of vertex colouring
- The parameterised complexity of list problems on graphs of bounded treewidth
- Consensus models: computational complexity aspects in modern approaches to the list coloring problem
- Generation of colour-constrained spanning trees with application in symbolic circuit analysis
- Open Problems on Graph Coloring for Special Graph Classes
- On the complexity of some colorful problems parameterized by treewidth
- Weighted coloring: further complexity and approximability results
- Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
- Answering conjunctive queries with inequalities
- The \(d\)-precoloring problem for \(k\)-degenerate graphs
- Bandwidth consecutive multicolorings of graphs
- On coloring problems with local constraints
- List total colorings of series-parallel graphs
- List homomorphism: beyond the known boundaries
This page was built for publication: Generalized coloring for tree-like graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363645)
