Maximizing proper colorings on graphs

DOI10.1016/j.jctb.2015.07.002zbMath1319.05054arXiv1411.4364OpenAlexW1608610748MaRDI QIDQ490999

Jie Ma, Humberto Naves

Publication date: 21 August 2015

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

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

zbMATH Keywords

chromatic polynomialTurán graphLazebnik's conjectureLinial-Wilf problem

Mathematics Subject Classification ID

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

Related Items (8)

Counting dominating sets and related structures in graphs ⋮ The Extremality of 2-Partite Turán Graphs with Respect to the Number of Colorings ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Maximizing the number of \(x\)-colorings of 4-chromatic graphs ⋮ Extremal colorings and independent sets ⋮ The maximum number of colorings of graphs of given order and size: a survey ⋮ Maximum number of colourings: 4-chromatic graphs ⋮ Tomescu's Graph Coloring Conjecture for $\ell$-Connected Graphs

Cites Work

• Unnamed Item
• The clique density theorem
• An extremal property of Turán graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Legal coloring of graphs
• Graphs with a small number of nonnegative eigenvalues
• Acyclic orientations of graphs
• 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
• New upper bounds for the greatest number of proper colorings of a (V,E)‐graph
• Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
• An Extremal Property of Turán Graphs, II
• Maximum number of colorings of (2k, k²)‐graphs

This page was built for publication: Maximizing proper colorings on graphs