Extremal H‐Colorings of Graphs with Fixed Minimum Degree

DOI10.1002/jgt.21820zbMath1320.05038arXiv1307.5919OpenAlexW2172837624MaRDI QIDQ5251205

John Engbers

Publication date: 22 May 2015

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

enumerationindependent setgraph homomorphism\(H\)-coloringproper coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Extremal \(H\)-colorings of trees and 2-connected graphs ⋮ 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
• \(H\)-colouring bipartite graphs
• Independent sets in graphs with given minimum degree
• Two problems on independent sets in graphs
• The number of independent sets in a graph with small maximum degree
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Legal coloring of graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Entropy, independent sets and antichains: A new approach to Dedekind’s problem
• Maximizing the number of q -colorings
• The Bipartite Swapping Trick on Graph Homomorphisms
• The Multistate Hard Core Model on a Regular Tree
• The Number of Independent Sets in a Regular Graph
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• Markov random field models of multicasting in tree networks
• Maximizing H‐Colorings of a Regular Graph
• Extremal graphs for homomorphisms
• On Independent Sets in Graphs with Given Minimum Degree
• Extremal Graphs for Homomorphisms II
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

This page was built for publication: Extremal H‐Colorings of Graphs with Fixed Minimum Degree