2026-08-06T12:45:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19338 2024-03-06T11:03:48Z ddc:004 open_access

Coloring and Recognizing Mixed Interval Graphs Gutowski, Grzegorz Junosza-Szaniawski, Konstanty Klesen, Felix Rzążewski, Paweł Wolff, Alexander Zink, Johannes Interval Graphs Mixed Graphs Graph Coloring A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Grzegorz Gutowski and Konstanty Junosza-Szaniawski and Felix Klesen and Paweł Rzążewski and Alexander Wolff and Johannes Zink 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.36 urn:nbn:de:0030-drops-193388 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36 eng https://creativecommons.org/licenses/by/4.0/legalcode