Oriented coloring on recursively defined digraphs

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G=(V,A) is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows, that finding the chromatic number of an oriented graph is an NP-hard problem. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.

Review text

Summary: Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented \(k\)-coloring of an oriented graph \(G = (V, A)\) is a partition of the vertex set \(V\) into \(k\) independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph \(G\) is the smallest \(k\) such that \(G\) allows an oriented \(k\)-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows that finding the chromatic number of an oriented graph is an NP-hard problem, too. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Oriented coloring on recursively defined digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003341)