English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A mixed graph has a set of vertices, a set of undirected egdes, and a set ofdirected arcs. A proper coloring of a mixed graph $G$ is a function $c$ thatassigns to each vertex in $G$ a positive integer such that, for each edge $uv$in $G$, $c(u) \ne c(v)$ and, for each arc $uv$ in $G$, $c(u) < c(v)$. For amixed graph $G$, the chromatic number $\chi(G)$ is the smallest number ofcolors in any proper coloring of $G$. A directional interval graph is a mixedgraph whose vertices correspond to intervals on the real line. Such a graph hasan edge between every two intervals where one is contained in the other and anarc between every two overlapping intervals, directed towards the interval thatstarts and ends to the right.  Coloring such graphs has applications in routing edges in layered orthogonalgraph drawing according to the Sugiyama framework; the colors correspond to thetracks for routing the edges. We show how to recognize directional intervalgraphs, and how to compute their chromatic number efficiently. On the otherhand, for mixed interval graphs, i.e., graphs where two intersecting intervalscan be connected by an edge or by an arc in either direction arbitrarily, weprove that computing the chromatic number is NP-hard.

Coloring Mixed and Directional Interval Graphs