An inequality for the chromatic number of a graph

DOI10.1016/S0021-9800(68)80081-XzbMath0171.44901OpenAlexW2094122556WikidataQ57259030 ScholiaQ57259030MaRDI QIDQ5558479

Herbert S. Wilf, George Szekeres

Publication date: 1967

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

Full work available at URL: https://doi.org/10.1016/s0021-9800(68)80081-x

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (53)

Chromatic scheduling and frequency assignment ⋮ On indicated chromatic number of graphs ⋮ Heawood inequalities ⋮ Dense trees: a new look at degenerate graphs ⋮ Some generalizations of theorems on vertex coloring ⋮ Bounds on eigenvalues and chromatic numbers ⋮ The book thickness of a graph ⋮ Critically partitionable graphs. I ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ Inductive graph invariants and approximation algorithms ⋮ Consecutive colorings of graphs ⋮ Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts ⋮ Towards the Chen-Raspaud conjecture ⋮ Directed domination in oriented graphs ⋮ Efficient deterministic algorithms for embedding graphs on books ⋮ Group connectivity and group colorings of graphs --- a survey ⋮ The signed \(k\)-domination number of directed graphs ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ A comparison of bounds for the chromatic number of a graph ⋮ Chromatic optimisation: Limitations, objectives, uses, references ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Improved bounds for the chromatic index of graphs and multigraphs ⋮ Uncolorable mixed hypergraphs ⋮ Unnamed Item ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ A sequential elimination algorithm for computing bounds on the clique number of a graph ⋮ Best monotone degree conditions for graph properties: a survey ⋮ An inequality for the group chromatic number of a graph ⋮ Independent sets in graphs ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ Graph signatures: identification and optimization ⋮ Analytic methods for uniform hypergraphs ⋮ New potential functions for greedy independence and coloring ⋮ Bounds and conjectures for the signless Laplacian index of graphs ⋮ Chromatic number and skewness ⋮ Graph theory ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Threshold-based network structural dynamics ⋮ Threshold-based network structural dynamics ⋮ Chromatic partitions of a graph ⋮ Domination in Digraphs ⋮ Lower bounds on the signed domination numbers of directed graphs ⋮ The subchromatic number of a graph ⋮ Sum coloring and interval graphs: A tight upper bound for the minimum number of colors ⋮ Colorings in digraphs from the spectral radius ⋮ Efficient bounds for the stable set, vertex cover and set packing problems ⋮ Inequalities involving the irredundance number of a graph ⋮ On graphs \(G\) for which all large trees are \(G\)-good ⋮ Upper bound for linear arboricity ⋮ Estimation of sparse hessian matrices and graph coloring problems ⋮ A Relaxed Version of the Erdős–Lovász Tihany Conjecture ⋮ Relaxed chromatic numbers of graphs

This page was built for publication: An inequality for the chromatic number of a graph