Results 71 to 80 of about 331 (182)

Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications

Journal of the London Mathematical Society, Volume 112, Issue 4, October 2025.
Abstract In 2006, Marcus and Tardos proved that if A1,⋯,An$A^1,\dots,A^n$ are cyclic orders on some subsets of a set of n$n$ symbols such that the common elements of any two distinct orders Ai$A^i$ and Aj$A^j$ appear in reversed cyclic order in Ai$A^i$ and Aj$A^j$, then ∑i|Ai|=O(n3/2logn)$\sum _{i} |A^i|=O(n^{3/2}\log n)$.
Barnabás Janzer, Oliver Janzer, Abhishek Methuku, Gábor Tardos   +3 more
wiley   +1 more source

Path Eccentricity and Forbidden Induced Subgraphs

The path eccentricity of a connected graph $G$ is the minimum integer $k$ such that $G$ has a path such that every vertex is at distance at most $k$ from the path. A result of Duffus, Jacobson, and Gould from 1981 states that every connected $\{\text{claw}, \text{net}\}$-free graph $G$ has a Hamiltonian path, that is, $G$ has path eccentricity $0 ...
Cichacz, Sylwia, Hilaire, Claire, Masařík, Tomáš, Masaříková, Jana, Milanič, Martin   +4 more
openaire   +2 more sources

Weighted Turán Theorems With Applications to Ramsey‐Turán Type of Problems

Journal of Graph Theory, Volume 110, Issue 1, Page 59-71, September 2025.
ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems.
József Balogh, Domagoj Bradač, Bernard Lidický   +2 more
wiley   +1 more source

Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws [PDF]

, 2020
Karl Heuer, Deniz Sarikaya
openalex   +1 more source

Pairs of forbidden induced subgraphs for homogeneously traceable graphs

Discrete Mathematics, 2012
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Li, Binlong, Li, Binlong, Broersma, Haitze J., Zhang, Shenggui   +3 more
openaire   +1 more source

Reconfiguration of vertex colouring and forbidden induced subgraphs

European Journal of Combinatorics
10 ...
Manoj Belavadi, Kathie Cameron, Owen Merkel   +2 more
openaire   +3 more sources

On the forbidden induced subgraph probe and sandwich problems

Discrete Applied Mathematics, 2018
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Couto, Fernanda, Faria, Luerbio, Gravier, Sylvain, Klein, Sulamita   +3 more
openaire   +3 more sources

Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs

Informatika, 2018
A hypergraph is called k-chromatic if its vertex set can be partitioned into at most k pairwise disjoint subsets when each subset has no more than two common vertices with every edge of the hypergraph.
T. V. Lubasheva
doaj  

Relative timing information and orthology in evolutionary scenarios. [PDF]

Algorithms Mol Biol, 2023
Schaller D, Hartmann T, Lafond M, Stadler PF, Wieseke N, Hellmuth M.   +5 more
europepmc   +1 more source

On forbidden induced subgraphs for K_{1,3}-free perfect graphs

, 2019
Considering connected $K_{1,3}$-free graphs with independence number at least $3$, Chudnovsky and Seymour (2010) showed that every such graph, say $G$, is $2 $-colourable where $ $ denotes the clique number of $G$. We study $(K_{1,3}, Y)$-free graphs, and show that the following three statements are equivalent. (1) Every connected $(K_{1,3}, Y)$-free
Brause, Christoph, Holub, Přemysl, Kabela, Adam, Ryjáček, Zdeněk, Schiermeyer, Ingo, Vrána, Petr   +5 more
openaire   +3 more sources