The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings

DOI10.1137/22m1511990zbMath1526.05048arXiv2201.00036OpenAlexW4387939784MaRDI QIDQ6069431

Unnamed Author

Publication date: 14 November 2023

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

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

zbMATH Keywords

chromatic polynomialTurán graphLinial-Wilf problemLazebnik conjecturemaximizing number of colorings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Maximizing proper colorings on graphs
• An extremal property of Turán graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• The maximum number of colorings of graphs of given order and size: a survey
• Some corollaries of a theorem of Whitney on the chromatic polynomial
• Maximizing the number of q -colorings
• Turán Graphs and the Number of Colorings
• A theoretical analysis of backtracking in the graph coloring problem
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• An Extremal Property of Turán Graphs, II
• Maximum number of colorings of (2k, k²)‐graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings