Tight Chromatic Number for a class of Graphs with two forbidden subgraphs
Dhurandhar, Medha
Original · EN
Although the chromatic number of a graph is not known in general, attempts have been made to find good bounds for the number. Here we prove that for a graph G with two forbidden subgraphs and maximum degree less than or equal to 2ω - 3, χ equals its maximum clique size. We also give examples to show that the condition is necessary.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.