ﻻ يوجد ملخص باللغة العربية
The second authors $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chi leq lceil frac 12 (Delta+1+omega)rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $chi$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.
In 1998 the second author proved that there is an $epsilon>0$ such that every graph satisfies $chi leq lceil (1-epsilon)(Delta+1)+epsilonomegarceil$. The first author recently proved that any graph satisfying $omega > frac 23(Delta+1)$ contains a sta
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyc
Given two independent sets $I, J$ of a graph $G$, and imagine that a token (coin) is placed at each vertex of $I$. The Sliding Token problem asks if one could transform $I$ to $J$ via a sequence of elementary steps, where each step requires sliding a
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we