Results 101 to 110 of about 10,088 (246)
Forbidden subgraphs and Hamiltonian properties of graphs
Discrete Mathematics, 1982 AbstractVarious sufficient conditions are given, in terms of forbidden subgraphs, that imply a graph is either homogeneously traceable, hamiltonian or pancyclic.
Michael S. Jacobson, Ronald J. Gould
openaire +3 more sources
Single‐conflict colorings of degenerate graphs
Journal of Graph Theory, Volume 109, Issue 2, Page 170-183, June 2025.Abstract We consider the single‐conflict coloring problem, a graph coloring problem in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex coloring such that no two adjacent vertices receive a pair of colors forbidden at an edge joining them.
Peter Bradshaw, Tomáš Masařík
wiley +1 more source
Subgraphs and Colourability of Locatable Graphs [PDF]
, 2014 We study a game of pursuit and evasion introduced by Seager in 2012, in which a cop searches the robber from outside the graph, using distance queries. A graph on which the cop wins is called locatable.
Johnson, Richard A. B., Koch, Sebastian
core
Rainbow vertex-connection and forbidden subgraphs
Discussiones Mathematicae Graph Theory, 2018 11 ...
Xueliang Li, Wenjing Li, Jingshu Zhang
openaire +4 more sources
Optimizing Staircase Motifs in Biofabric Network Layouts
Computer Graphics Forum, Volume 44, Issue 3, June 2025.Abstract Biofabric is a novel method for network visualization, with promising potential to highlight specific network features. Recent studies emphasize the importance of staircase motifs — equivalent to fans or stars in node‐link diagrams — within Biofabric.
Sara Di Bartolomeo +2 more
wiley +1 more source
Three forbidden subgraphs for line graphs
Discrete Mathematics, 2002 Beineke has shown that a connected graph \(G\) is a line graph iff it does not contain any of nine graphs drawn in a figure as an induced subgraph. This result was improved by Šoltés: \(G\) is a line graph if it does not contain any of the first seven graphs given by Beineke as an induced subgraph and is not isomorphic to any of five additional drawn ...
Yuansheng Yang, Chunli Wang, Jianhua Lin
openaire +2 more sources
Odd chromatic number of graph classes
Journal of Graph Theory, Volume 108, Issue 4, Page 722-744, April 2025.Abstract A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$.
Rémy Belmonte +3 more
wiley +1 more source
Natural Sciences, Volume 5, Issue 1-2, April 2025.The most common cystic fibrosis‐causing F508del mutation is located in the first nucleotide‐binding domain (hNBD1) of the human cystic fibrosis transmembrane conductance regulator (hCFTR). The ATP‐dependent weakest noncovalent bridge in isolated hNBD1 is found between two specific bold residues in the biggest thermo‐ring (highlighted in red) at or near
Guangyu Wang
wiley +1 more source
Span programs and quantum algorithms for st-connectivity and claw detection
, 2012 We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems.
A. Ambainis +4 more
core +1 more source
The number of graphs without forbidden subgraphs
Journal of Combinatorial Theory, Series B, 2004 \textit{P. Erdős, P. Frankl} and \textit{V. Rödl} [Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)] proved that for a family \({\mathcal L}\) of graphs the number of labeled graphs of order \(n\) that do not contain a graph in \({\mathcal L}\) as a subgraph is \(2^{\frac{1}{2}\left(1-\frac{1}{p}\right)n^2+o(n^2)}\) where \(p=\min_{L\in {\mathcal L ...
Béla Bollobás +2 more
openaire +2 more sources