Results 61 to 70 of about 10,088 (246)
Towards an Isomorphism Dichotomy for Hereditary Graph Classes [PDF]
, 2014 In this paper we resolve the complexity of the isomorphism problem on all but finitely many of the graph classes characterized by two forbidden induced subgraphs.
Schweitzer, Pascal
core +3 more sources
A general framework on conditions for constraint‐based causal learning
Scandinavian Journal of Statistics, EarlyView.Abstract Most constraint‐based causal learning algorithms provably return the correct causal graph under certain correctness conditions, such as faithfulness. By representing any constraint‐based causal learning algorithm using the notion of a property, we provide a general framework to obtain and study correctness conditions for these algorithms. From
Kai Z. Teh, Kayvan Sadeghi, Terry Soo
wiley +1 more source
Proper circular arc graphs as intersection graphs of paths on a grid [PDF]
, 2018 In this paper we present a characterisation, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend (turn)
Galby, Esther +2 more
core +2 more sources
On coloring digraphs with forbidden induced subgraphs
Journal of Graph Theory, 2022 AbstractWe prove a conjecture by Aboulker, Charbit, and Naserasr by showing that every oriented graph in which the out‐neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden ...
openaire +3 more sources
Indiscernibles in monadically NIP theories
Bulletin of the London Mathematical Society, EarlyView.Abstract We prove various results around indiscernibles in monadically NIP theories. First, we provide several characterizations of monadic NIP in terms of indiscernibles, mirroring previous characterizations in terms of the behavior of finite satisfiability. Second, we study (monadic) distality in hereditary classes and complete theories.
Samuel Braunfeld, Michael C. Laskowski
wiley +1 more source
Problems in extremal graph theory [PDF]
, 2010 We consider a variety of problems in extremal graph and set theory. The {\em chromatic number} of $G$, $\chi(G)$, is the smallest integer $k$ such that $G$ is $k$-colorable.
Ozkahya, Lale
core
Graphs that are not pairwise compatible: A new proof technique (extended abstract) [PDF]
, 2018 A graph G = (V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dminand dmax, dmin≤ dmax, such that each node u∈V is uniquely associated to a leaf of T and there is an edge (u, v) ∈ E if
Baiocchi, Pierluigi +3 more
core +1 more source
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs [PDF]
Journal of Graph Theory, 2012 The Caccetta-Haggkvist conjecture made in 1978 asserts that every orgraph on n vertices without oriented cycles of length <= l must contain a vertex of outdegree at most (n-1)/l. It has a rather elaborate set of (conjectured) extremal configurations. In this paper we consider the case l=3 that received quite a significant attention in the literature.
openaire +3 more sources
Assigning airport ground handling operations: a data‐driven matheuristic
International Transactions in Operational Research, Volume 33, Issue 1, Page 359-383, January 2026.Abstract In this paper, we study a problem in the crossover between vehicle routing and scheduling problems. The multi‐trip capacitated vehicle routing and scheduling problem with time windows and meal breaks is extended to a heterogeneous fleet of trucks and drivers, with qualifications and different loading patterns.
Alexandre Dupaquis +5 more
wiley +1 more source
Decomposition of 4k-regular graphs into k 4-regular K5-free and (K5−e)-free subgraphs [PDF]
Discrete Mathematics Letters, 2021 Rachel Johnson +4 more
doaj +1 more source