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

zbMATH Keywords

directed graphstreewidth duality\(H\)-coloring problem

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

(25)

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

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)