scientific article; zbMATH DE number 932194

DOI10.1002/(SICI)1097-0118(199610)23:2%3C151::AID-JGT6%3E3.0.CO;2-SMaRDI QIDQ4894618zbMATH OpenFDO

Authors J. Nešetřil, Xuding Zhu

Publication date 7 October 1996

Full work available at URL https://doi.org/10.1002/(SICI)1097-0118(199610)23:2%3C151::AID-JGT6%3E3.0.CO;2-S

zbMATH Keywords

\(H\)-coloring problemdirected graphstreewidth duality

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Duality and Polynomial Testing of Tree Homomorphisms
• Dichotomy for bounded degree \(H\)-colouring
• On digraph coloring problems and treewidth duality
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

Cited in

(26)

• A partial k-arboretum of graphs with bounded treewidth
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Colorings and girth of oriented planar graphs
• Homomorphisms from sparse graphs with large girth.
• On universal graphs for planar oriented graphs of a given girth
• High-girth graphs avoiding a minor are nearly bipartite
• On the density of \(C_7\)-critical graphs
• On digraph coloring problems and treewidth duality
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• Trimming weighted graphs of bounded treewidth
• Duality and Polynomial Testing of Tree Homomorphisms
• scientific article; zbMATH DE number 1420226 (Why is no real title available?)
• Canonizing Graphs of Bounded Tree Width in Logspace
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
• Treewidth of display graphs: bounds, brambles and applications
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• scientific article; zbMATH DE number 6292751 (Why is no real title available?)
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• A managed Bayesian risk approach for decision making alternatives
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Graphs of bounded twin-width are quasi-polynomially -bounded
• Fractional coloring planar graphs under Steinberg-type conditions
• On ( n , m )-chromatic numbers of graphs with bounded sparsity parameters
• On the density of C₇-critical graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4894618)