RECORD
Oriented coloring on recursively defined digraphs
Data Structures and Algorithms · Submitted 2 Apr 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Coloring is one of the most famous problems in graph theory. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s1 | The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. | gap 0.52 | 0.04 | 0.01 | asserted 1.00 |
| s2 | 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. | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s3 | The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. | background 1.00 | 0.10 | 0.03 | asserted 1.00 |
| s4 | Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. | background 0.96 | 0.14 | 0.03 | asserted 1.00 |
| s5 | It follows, that finding the chromatic number of an oriented graph is an NP-hard problem. | background 0.60 | 0.18 | 0.04 | asserted 1.00 |
| s6 | This motivates to consider the problem on oriented co-graphs. | background 0.30 | 0.11 | 0.03 | asserted 0.71 |
| s7 | 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. | contribution 0.90 | 0.96 | 0.73 | asserted 1.00 |
| s8 | 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. | contribution 0.52 | 0.94 | 0.10 | asserted 1.00 |
| s9 | It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. | result 0.99 | 0.89 | 0.39 | asserted 1.00 |
| s10 | We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time. | result 0.74 | 0.93 | 0.07 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.