Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable.
Antisymmetric flows and strong colourings of oriented graphs
The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number (as the modular version...
Cutwidth of the de Bruijn graph
Strong Chromatic Index Of Planar Graphs With Large Girth
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
On bandwidth, cutwidth, and quotient graphs
Partitioning planar graph of girth 5 into two forests with maximum degree 4
Given a graph , if we can partition the vertex set into two nonempty subsets and which satisfy and , then we say has a -partition. And we say admits an -partition if and are both forests whose maximum degree is at most and , respectively. We show that every planar graph with girth at least 5 has an -partition.
Three-and-more set theorems
In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erdős-de Bruijn, Katětov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a “small” coloring. These results are also related to graph homomorphisms and (oriented) colorings.
Page 1