On an upper bound of the graph's chromatic number, depending on the graph's degree and density

DOI10.1016/0095-8956(77)90037-5zbMath0336.05104OpenAlexW2080547399MaRDI QIDQ1229732

Alexandr V. Kostochka, Oleg V. Borodin

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1016/0095-8956(77)90037-5

Mathematics Subject Classification ID

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

Related Items

The $m$-degenerate chromatic number of a digraph, Chromatic properties of the Pancake graphs, Problems and results on judicious partitions, Painting squares in $\Delta^2-1$ shades, Minimal orientations of colour critical graphs, Ramsey-nice families of graphs, Brooks' Theorem and Beyond, A Note on Hitting Maximum and Maximal Cliques With a Stable Set, On a conjecture of Schweser and Stiebitz, New upper bounds for the chromatic number of a graph, On 1-improper 2-coloring of sparse graphs, List-Coloring Claw-Free Graphs with $\Delta-1$ Colors, Graphs with $\chi=\Delta$ Have Big Cliques, Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors, Combinatorics. Abstracts from the workshop held January 1--7, 2023, On Brooks' Theorem for Sparse Graphs, A note on $\Delta$-critical graphs, A note on Reed's conjecture for triangle-free graphs, The Fractional Chromatic Number of $\boldsymbol{K_{\Delta }}$-Free Graphs, Large cliques in graphs with high chromatic number, The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree, Special issue in honour of Landon Rabern, Coloring $\{ P 2 \cup P 3 , \operatorname{house} \} $-free graphs with $\Delta - 1$ colors, Strengthening Brooks' chromatic bound on $P_6$-free graphs, Borodin-Kostochka conjecture holds for odd-hole-free graphs, Coloring hammer-free graphs with $\Delta - 1$ colors, Partitioning of a graph into induced subgraphs not containing prescribed cliques, Majority choosability of countable graphs, On triangle-free list assignments, Graph partitions under average degree constraint, On the Grundy and $b$-chromatic numbers of a graph, Unnamed Item, Randomly colouring graphs (a combinatorial view), Improvement on Brooks' chromatic bound for a class of graphs, Colouring graphs when the number of colours is almost the maximum degree, Coloring a graph with $\Delta-1$ colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, Partitions of multigraphs under minimum degree constraints, A note on the independence number of triangle-free graphs. II, Destroying Noncomplete Regular Components in Graph Partitions, SELF-STABILIZING ALGORITHMS FOR UNFRIENDLY PARTITIONS INTO TWO DISJOINT DOMINATING SETS, Unnamed Item, New potential functions for greedy independence and coloring, Satisfactory graph partition, variants, and generalizations, On a theorem about vertex colorings of graphs, Graph theory (algorithmic, algebraic, and metric problems), On the Grundy Number of a Graph, Another bound on the chromatic number of a graph, Vertex partition of hypergraphs and maximum degenerate subhypergraphs, Chromatic number, girth and maximal degree, Coloring Sparse Hypergraphs, Alliances and Related Domination Parameters, Self-Stabilizing Domination Algorithms, Borodin-Kostochka's conjecture on $(P_5,C_4)$-free graphs, Unfriendly partitions of a graph, Partitioning a graph into alliance free sets, Coloring Graphs with Dense Neighborhoods, A strengthening of Brooks' theorem, A note on coloring vertex-transitive graphs, Distributed coloring algorithms for triangle-free graphs, Judicious partitions of graphs, On cylindrical graph construction and its applications

Cites Work