There has been extensive research on cycle lengths in graphs with large minimum degree.
In this paper, we obtain several results that are tight in this area. Let G be a graph with …

Let k and r be two integers with k≥ 2 and k≥ r≥ 1. In this paper we show that (1) if a
strongly connected digraph D contains no directed cycle of length 1 modulo k, then D is k …

We propose two strategies for Presenter in on-line graph coloring games. The first one
constructs bipartite graphs and forces any on-line coloring algorithm to use 2\log _2 n-10 …

In 1976, Bondy proved that the chromatic number of a graph G is at most its circumference,
the length of a longest cycle. In 1992, Tuza proved that, for any integer k≥ 2, if a graph G …

Tuza [1992] proved that a graph with no cycles of length congruent to $1 $ modulo $ k $ is $
k $-colorable. We prove that if a graph $ G $ has an edge $ e $ such that $ Ge $ is $ k …

In this paper we obtain the following upper bound for the chromatic number of a graph G, χ
(G) G,χ(G): Let GG be a connected graph with at least one cycle and kk an integer, with k≥ 2 …

Brooks' Theorem from 1941 is a cornerstone in graph theory. Until then graph coloring
theory was centered around planar graphs and the four color problem. Brooks' Theorem was …

Problem. Kolorowanie online to gra pomiędzy Prezenterem i Algorytmem. Gra rozgrywana
jest w rundach na planszy, która na początku jest pustym grafem. W każdej kolejnej rundzie …

Let 𝑁 be a network (or linear graph) such that at each node not more than 𝑛 lines meet
(where 𝑛> 2), and no line has both ends at the same node. Suppose also that no connected …