Large deviations in randomly coloured random graphs.
Lattices of relative colour-families and antivarieties
We consider general properties of lattices of relative colour-families and antivarieties. Several results generalise the corresponding assertions about colour-families of undirected loopless graphs, see [1]. Conditions are indicated under which relative colour-families form a lattice. We prove that such a lattice is distributive. In the class of lattices of antivarieties of relation structures of finite signature, we distinguish the most complicated (universal) objects. Meet decompositions in lattices...
Le théorème des quatre couleurs : notice historique et aperçu technique
Le théorème du coloriage des cartes (ex-conjecture de Heawood et conjecture des quatre couleurs)
Line-Coloring of Signed Graphs.
List 2-distance -coloring of planar graphs with girth 6 and .
List coloring of complete multipartite graphs
The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.
List edge-colorings of series-parallel graphs.
List -coloring of sparse plane graphs.
Localization of jumps of the point-distinguishing chromatic index of
The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of is found.
Locally bounded k-colorings of trees
Given a tree T with n vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of T respecting local (i.e., associated with p prespecified subsets of vertices) color bounds can be solved in O(n6p-1logn) time. We also show that our algorithm can be adapted to the case of k-colorings for fixed k.
Long heterochromatic paths in edge-colored graphs.
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring.
Lower bounds for the colored mixed chromatic number of some classes of graphs
A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph is defined as the smallest order of a colored mixed graph such that there exists a (color preserving) homomorphism from to . These notions were introduced by Nešetřil and Raspaud in Colored homomorphisms of colored mixed graphs, J. Combin. Theory Ser. B 80 (2000), no. 1, 147–155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic...