Advanced Search

One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound $\chi (G\times H)\ge min\{{\chi }_f\left(G\right),{\chi }_f\left(H\right)\}$ should always hold. We prove that $\chi (G\times H)\ge \frac{1}{2}min\{{\chi }_f\left(G\right),{\chi }_f\left(H\right)\}$.

We prove that for any $c\ge 5$, there exists an infinite family ${\left(G_n\right)}_{n\in \mathbb{N}}$ of graphs such that $\chi \left(G_n\right)>c$ for all $n\in \mathbb{N}$ and $\chi (G_m\times G_n)\le c$ for all $m\ne n$. These counterexamples to Hedetniemi’s conjecture show that the Boolean lattice of exponential graphs with $K_c$ as a base is infinite for $c\ge 5$.

The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that...

We show that the pairs $T,D_T$ where T is a tree and $D_T$ its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.

The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.

We present an algebraic treatment of the correspondence of gaps and dualities in partial ordered classes induced by the morphism structures of certain categories which we call Heyting (such are for instance all cartesian closed categories, but there are other important examples). This allows to extend the results of [14] to a wide range of more general structures. Also, we introduce a notion of combined dualities and discuss the relation of their structure to that of the plain ones.

We provide the list of all paths with at most $16$ arcs with the property that if a graph $G$ admits an orientation $\overrightarrow{G}$ such that one of the paths in our list admits no homomorphism to $\overrightarrow{G}$, then $G$ is $3$-colourable.

The arc graph $\delta \left(G\right)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $\delta \left(G\right)$ join consecutive arcs of $G$. In 1981, S. Poljak and V. Rödl characterized the chromatic number of $\delta \left(G\right)$ in terms of the chromatic number of $G$ when $G$ is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the...