Advanced Search

The oriented chromatic number of an oriented graph ${}^{\to }G$ is the minimum order of an oriented graph ${}^{\to }H$ such that ${}^{\to }G$ admits a homomorphism to ${}^{\to }H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph ${}^{\to }U$ such that every orientation ${}^{\to }G$ of G admits a homomorphism to ${}^{\to }U$. We give some properties...

An incidence in a graph G is a pair (v, e) with v ∈ V (G) and e ∈ E(G), such that v and e are incident. Two incidences (v, e) and (w, f) are adjacent if v = w, or e = f, or the edge vw equals e or f. The incidence chromatic number of G is the smallest k for which there exists a mapping from the set of incidences of G to a set of k colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid Tm,n = Cm2Cn equals 5 when...

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and...

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^n$ vertices, $n\ge 1$, is $n$. The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted...

A homomorphism of an oriented graph $G=(V,A)$ to an oriented graph $G^{\text{'}}=(V^{\text{'}},A^{\text{'}})$ is a mapping $\varphi$ from $V$ to $V^{\text{'}}$ such that $\varphi \left(u\right)\varphi \left(v\right)$ is an arc in $G^{\text{'}}$ whenever $uv$ is an arc in $G$. A homomorphism of $G$ to $G^{\text{'}}$ is said to be $T$-preserving for some oriented graph $T$ if for every connected subgraph $H$ of $G$ isomorphic to a subgraph of $T$, $H$ is isomorphic to its homomorphic image in $G^{\text{'}}$. The $T$-preserving oriented chromatic number ${\overrightarrow{\chi }}_T\left(G\right)$ of an oriented graph $G$ is the minimum number of vertices in an oriented graph $G^{\text{'}}$ such that there exists a $T$-preserving...

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.