scientific article; zbMATH DE number 932194

DOI10.1002/(SICI)1097-0118(199610)23:2%3C151::AID-JGT6%3E3.0.CO;2-SzbMATH Open0858.05045MaRDI QIDQ4894618FDOQ4894618

Authors: J. Nešetřil, Xuding Zhu 

Publication date: 7 October 1996

Title of this publication is not available (Why is that?)

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

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)

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
• Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• A partial k-arboretum of graphs with bounded treewidth
• Title not available (Why is that?)
• On \(( n , m )\)-chromatic numbers of graphs with bounded sparsity parameters
• Colorings and girth of oriented planar graphs
• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Homomorphisms from sparse graphs with large girth.
• A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
• On universal graphs for planar oriented graphs of a given girth
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• On the density of \(C_7\)-critical graphs
• 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
• On the density of \(C_7\)-critical graphs
• High-girth graphs avoiding a minor are nearly bipartite
• A managed Bayesian risk approach for decision making alternatives
• Title not available (Why is that?)
• 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)