New upper bounds for the chromatic number of a graph

DOI<117::AID-JGT6>3.0.CO;2-7 10.1002/1097-0118(200102)36:2<117::AID-JGT6>3.0.CO;2-7zbMath0971.05041OpenAlexW4256383760MaRDI QIDQ2707978

Ladislav Stacho

Publication date: 21 October 2001

Full work available at URL: https://doi.org/10.1002/1097-0118(200102)36:2<117::aid-jgt6>3.0.co;2-7

zbMATH Keywords

chromatic numbermaximum degreeBrooks' theorem

Mathematics Subject Classification ID

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

Related Items

Index of parameters of iterated line graphs, Computational aspects of greedy partitioning of graphs, Unnamed Item, New potential functions for greedy independence and coloring, Algorithmic bounds for the chromatic number†, Three new upper bounds on the chromatic number

Cites Work

• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Some simplified NP-complete graph problems
• Covering the vertex set of a graph with subgraphs of smaller degree
• A bound on the chromatic number of a graph
• On Brooks' Theorem for Sparse Graphs