Oriented Vertex and Arc Coloring of Edge Series-Parallel Digraphs

Frank Gurski (), Dominique Komander () and Marvin Lindemann ()
Additional contact information
Frank Gurski: University of Düsseldorf
Dominique Komander: University of Düsseldorf
Marvin Lindemann: University of Düsseldorf

A chapter in Operations Research Proceedings 2021, 2022, pp 101-106 from Springer

Abstract: Abstract We study the oriented vertex and arc coloring problem on edge series-parallel digraphs which are related to the well known series-parallel graphs. The oriented class of edge series-parallel digraphs is recursively defined from pairs of vertices connected by a single arc and applying the parallel and series composition, which leads to specific orientations of undirected series-parallel graphs. We re-prove the known bound of 7 for the oriented chromatic number and the oriented chromatic index of series-parallel digraphs and we show that these bounds are tight even for edge series-parallel digraphs. Further, we give linear time solutions for computing the oriented chromatic number and the oriented chromatic index of minimal series-parallel digraphs and edge series-parallel digraphs.

Keywords: Series-parallel digraphs; Oriented vertex-coloring; Oriented arc-coloring; Linear time solutions (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-08623-6_16

Ordering information: This item can be ordered from
http://www.springer.com/9783031086236

DOI: 10.1007/978-3-031-08623-6_16

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().