Coloring the edges of a random graph without a monochromatic giant component.
Coloring with no 2-colored 's.
Colorings and nowhere-zero flows of graphs in terms of Berlekamp's switching game.
Colorings and orientations of matrices and graphs.
Colouring game and generalized colouring game on graphs with cut-vertices
For k ≥ 2 we define a class of graphs 𝓗 ₖ = {G: every block of G has at most k vertices}. The class 𝓗 ₖ contains among other graphs forests, Husimi trees, line graphs of forests, cactus graphs. We consider the colouring game and the generalized colouring game on graphs from 𝓗 ₖ.
Colouring graphs with prescribed induced cycle lengths
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have...
Colouring lattice points by real numbers.
Colouring of cycles in the de Bruijn graphs
We show that the problem of finding the family of all so called the locally reducible factors in the binary de Bruijn graph of order k is equivalent to the problem of finding all colourings of edges in the binary de Bruijn graph of order k-1, where each vertex belongs to exactly two cycles of different colours. In this paper we define and study such colouring for the greater class of the de Bruijn graphs in order to define a class of so called regular factors, which is not so difficult to construct....
Colouring planar mixed hypergraphs.
Colouring polytopic partitions in
Colouring polytopic partitions in
We consider face-to-face partitions of bounded polytopes into convex polytopes in for arbitrary and examine their colourability. In particular, we prove that the chromatic number of any simplicial partition does not exceed . Partitions of polyhedra in into pentahedra and hexahedra are - and -colourable, respectively. We show that the above numbers are attainable, i.e., in general, they cannot be reduced.
Colouring the petals of a graph.
Colouring vertices of plane graphs under restrictions given by faces
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other...
Combinatorial aspects of an exact sequence that is related to a graphs.
Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.
Combinatorial stacks and the four-color theorem
Combinatorics of Dyadic Intervals: Consistent Colourings
We study the problem of consistent and homogeneous colourings for increasing families of dyadic intervals. We determine when this problem can be solved and when it cannot.
Competitive colorings of oriented graphs.
Complete and almost complete minors in double-critical 8-chromatic graphs.
Complete and pseudocomplete colourings of a graph