Results 51 to 60 of about 10,088 (246)
AKCE International Journal of Graphs and Combinatorics, 2017 The extremal number or simply denotes the maximal number of edges in a graph on vertices with forbidden subgraphs and . The exact number of is only known for up to and . There are upper and lower bounds of for other values of .
Novi H. Bong
doaj +1 more source
On the chromatic number of (P_{5},windmill)-free graphs [PDF]
Opuscula Mathematica, 2017 In this paper we study the chromatic number of \((P_5, windmill)\)-free graphs. For integers \(r,p\geq 2\) the windmill graph \(W_{r+1}^p=K_1 \vee pK_r\) is the graph obtained by joining a single vertex (the center) to the vertices of \(p\) disjoint ...
Ingo Schiermeyer
doaj +1 more source
Complexity of Coloring Graphs without Paths and Cycles
, 2013 Let $P_t$ and $C_\ell$ denote a path on $t$ vertices and a cycle on $\ell$ vertices, respectively. In this paper we study the $k$-coloring problem for $(P_t,C_\ell)$-free graphs.
A. Brandstädt +16 more
core +1 more source
On the graph condition regarding the $F$-inverse cover problem [PDF]
, 2015 In their paper titled "On $F$-inverse covers of inverse monoids", Auinger and Szendrei have shown that every finite inverse monoid has an $F$-inverse cover if and only if each finite graph admits a locally finite group variety with a certain property. We
Szakács, Nóra
core +2 more sources
Heavy subgraph pairs for traceability of block-chains
Discussiones Mathematicae Graph Theory, 2014 A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type ...
Li Binlong +2 more
doaj +1 more source
A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2
Algorithms, 2021 Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of
Serafino Cicerone
doaj +1 more source
Minimal Obstructions for Partial Representations of Interval Graphs
, 2015 Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently.
C Lekkerkerker +17 more
core +1 more source
On Sequential Heuristic Methods for the Maximum Independent Set Problem
Discussiones Mathematicae Graph Theory, 2017 We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3].
Lê Ngoc C. +2 more
doaj +1 more source
On the 12-Representability of Induced Subgraphs of a Grid Graph
Discussiones Mathematicae Graph Theory, 2022 The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53].
Chen Joanna N., Kitaev Sergey
doaj +1 more source
The Price of Connectivity for Vertex Cover
, 2013 The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is
Camby, Eglantine +3 more
core +3 more sources