ﻻ يوجد ملخص باللغة العربية
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and sufficiently high degree, we prove the NP-completeness of acyclic r-colorings; our method also implies the known analogue for classical colorings. The proofs use high girth graphs with high arboricity and dichromatic numbers. High girth graphs and digraphs with high chromatic and dichromatic numbers have been well studied; we re-derive the results from a general result about relational systems, which also implies the similar fact about high girth and high arboricity used in the proofs. These facts concern graphs and digraphs of high girth and low degree; we contrast them by considering acyclic colorings of tournaments (which have low girth and high degree). We prove that even though acyclic two-colorability of tournaments is known to be NP-complete, random acyclically r-colorable tournaments allow recovering an acyclic r-coloring in deterministic linear time, with high probablity.
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyc
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if i
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such colo
An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$
We unify several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include, in addition to interval graphs, also adjusted interval digraphs, thre