Results 101 to 110 of about 9,740 (155)
3-Colourability and Forbidden Subgraphs
Electronic Notes in Discrete Mathematics, 2000 Abstract In this paper we investigate the chromatic aspects for graphs with forbidden induced subgraphs with emphasis on the question of 3-colourability. In the main part all possible pairs (A, B) of forbidden induced subgraphs, s.t. every A- and B -free graph is 3-colourable, are determined.
openaire +1 more source
Density theorems for bipartite graphs and related Ramsey-type results
, 2007 In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density.
Fox, Jacob, Sudakov, Benny
core +4 more sources
Forbidden Subgraph Problems with Predictions
CoRRIn the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected induced forbidden subgraph H at each point in time. To achieve this, an algorithm must, upon each occurrence of H, identify and irrevocably delete one or more vertices.
Hans-Joachim Böckenhauer +3 more
openaire +2 more sources
On Hereditary Helly classes of graphs
Discrete Mathematics & Theoretical Computer Science, 2008 In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively.
Marina Groshaus, Jayme Luiz Szwarcfiter
doaj
Line Graphs and Forbidden Induced Subgraphs
Journal of Combinatorial Theory, Series B, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hong-Jian Lai, Lubomír Soltés
openaire +1 more source
Eigenvalues and forbidden subgraphs I
Linear Algebra and its Applications, 2007 Some calculation errors in the first version are ...
openaire +3 more sources
Rainbow vertex-connection and forbidden subgraphs
Discussiones Mathematicae Graph Theory, 2018 11 ...
Li Wenjing, Li Xueliang, Zhang Jingshu
openaire +4 more sources
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.
Ronald J. Gould, Michael S. Jacobson
openaire +2 more sources
Small clique number graphs with three trivial critical ideals
Special Matrices, 2018 The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. Previously, they have been used in the understanding and characterizing of the graphs with critical group with few invariant factors ...
Alfaro Carlos A., Valencia Carlos E.
doaj +1 more source
$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses [PDF]
Discrete Mathematics & Theoretical Computer ScienceA graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs.
Fernando Esteban Contreras-Mendoza +1 more
doaj +1 more source