Extremal \(H\)-colorings of trees and 2-connected graphs

DOI10.1016/J.JCTB.2016.09.009zbMath1350.05033arXiv1506.05388OpenAlexW2228991476MaRDI QIDQ345129

John Engbers, David Galvin

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.05388

zbMATH Keywords

graph coloringgraph homomorphismsWidom-Rowlinson model\(H\)-coloring2-connected graphsLondon-Hoffman inequality

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Maximizing the number of \(x\)-colorings of 4-chromatic graphs ⋮ Maximizing and minimizing the number of generalized colorings of trees ⋮ Extremal colorings and independent sets ⋮ Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree ⋮ Maximum number of colourings: 4-chromatic graphs ⋮ Tomescu's Graph Coloring Conjecture for $\ell$-Connected Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Graph homomorphisms between trees
• Graphs with given number of cut vertices and extremal Merrifield-Simmons index
• The number of mappings of graphs, an ordering of graphs, and Muirhead's theorem
• Proof of London's conjecture on sums of elements of positive matrices
• A partially ordered set of functionals corresponding to graphs
• Non-negative matrices and Markov chains.
• Two inequalities in nonnegative symmetric matrices
• Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Three observations on nonnegative matrices
• Minimally 2-connected graphs.
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

This page was built for publication: Extremal \(H\)-colorings of trees and 2-connected graphs