Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs

DOI10.1016/j.disc.2011.08.030zbMath1244.05151MaRDI QIDQ432716

Mieczysław Borowiecki, Ewa Drgas-Burchardt

Publication date: 4 July 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.08.030

zbMATH Keywords

hypercube; graph homomorphism; Cartesian product; feedback vertex set; chordal bipartite graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C12: Distance in graphs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C76: Graph operations (line graphs, products, etc.)

Cites Work

• Feedback vertex set in hypercubes
• On a hypercube coloring problem
• Acyclic and \(k\)-distance coloring of the grid
• On the complexity of H-coloring
• Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network
• Decycling hypercubes
• An inequality involving the vertex arboricity and edge arboricity of a graph
• A survey of hereditary properties of graphs
• The Point-Arboricity of Planar Graphs
• Acyclic colorings of planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item