Adjusted Interval Digraphs |
| |
| Institution: | 1. School of Mathematics and Statistics, The University of New South Wales, Sydney, NSW 2052, Australia;2. Institut für Mathematik, Universität Rostock, Ulmenstraße 69, D-18051 Rostock, Germany;3. Institut für Finanzmathematik, Johannes Kepler Universität Linz, Altenbergerstraße 69, A-4040 Linz, Austria;1. Department of Mathematics, Kunming University of Science and Technology, Kunming 650500, Yunnan, China;2. School of Mathematical Sciences, University of Science and Technology of China, Wu Wen Tsun Key Laboratory of Mathematics, Chinese Academy of Science, Hefei 230026, Anhui, China;3. Department of Mathematics, The University of Hong Kong, Hong Kong, China;1. Department of Mathematics, Loyola College, Chennai 600034, India;2. Department of Mathematics, Stella Maris College, Chennai 600086, India;3. School of Advanced Sciences, VIT University, Chennai 600127, India;1. Departament d''Enginyeria Civil i Ambiental, Universitat Politècnica de Catalunya, Barcelona, Catalonia;2. Departament de Matemàtica, Universitat de Lleida, Igualada (Barcelona), Catalonia |
| |
| Abstract: | Interval digraphs were introduced by West et al. They can be recognized in polynomial time and admit a characterization in terms of incidence matrices. Nevertheless, they do not have a forbidden structure characterization nor a low-degree polynomial recognition algorithm.We introduce a new class of ‘adjusted interval digraphs,’ obtained by a slight change in the definition. We show that, by contrast, these digraphs have a natural forbidden structure characterization, parallel to a characterization for undirected graphs, and admit a simple recognition algorithm. We relate adjusted interval digraphs to a list homomorphism problem. Each digraph H defines a corresponding list homomorphism problem L-HOM(H). We observe that if H is an adjusted interval digraph, then the problem L-HOM(H) is polynomial time solvable, and conjecture that for all other reflexive digraphs H the problem L-HOM(H) is NP-complete. We present some preliminary evidence for the conjecture, including a proof for the special case of semi-complete digraphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
