Results 21 to 30 of about 331 (182)
Forbidden Induced Subgraphs and the Łoś–Tarski Theorem [PDF]
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2021 AbstractLet $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs ...
Chen, Yijia, Flum, Jörg
openaire +3 more sources
Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs [PDF]
Discrete Applied Mathematics, 2012 We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes, which applied to the case of two forbidden ...
Stefan Kratsch, Pascal Schweitzer
openalex +6 more sources
On characterizing game-perfect graphs by forbidden induced subgraphs
Contributions to Discrete Mathematics, 2012 A graph G is called g-perfect if, for any induced subgraph H of G, the game chromatic number of H equals the clique number of H. A graph G is called g-col-perfect if, for any induced subgraph H of G, the game coloring number of H equals the clique number of H. In this paper we characterize the classes of g-perfect resp. g-col-perfect graphs by a set of
Stephan Dominique Andres
openalex +3 more sources
Preorder induced by rainbow forbidden subgraphs [PDF]
Discrete MathematicsA subgraph $H$ of an edge-colored graph $G$ is rainbow if all the edges of $H$ receive different colors. If $G$ does not contain a rainbow subgraph isomorphic to $H$, we say that $G$ is rainbow $H$-free. For connected graphs $H_1$ and $H_2$, if every rainbow $H_1$-free edge-colored complete graph colored in sufficiently many colors is rainbow $H_2 ...
Shun‐ichi Maezawa, Akira Saito
openalex +3 more sources
Minimal Separators in Graph Classes Defined by Small Forbidden Induced Subgraphs [PDF]
, 2019 Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators.
Martin Milanič, Nevena Pivač
openalex +5 more sources
The Cop Number of Graphs with Forbidden Induced Subgraphs [PDF]
, 2019 In the game of Cops and Robber, a team of cops attempts to capture a robber on a graph $G$. Initially, all cops occupy some vertices in $G$ and the robber occupies another vertex. In each round, a cop can move to one of its neighbors or stay idle, after which the robber does the same.
Mingrui Liu
openalex +3 more sources
Line Graphs and Forbidden Induced Subgraphs
Journal of Combinatorial Theory, Series B, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lai, Hong-Jian, Šoltés, Ľubomír
openaire +1 more source
List-3-Coloring Ordered Graphs with a Forbidden Induced Subgraph
SIAM Journal on Discrete MathematicsAccepted manuscript; see DOI for journal ...
Sepehr Hajebi, Yanjia Li, Sophie Spirkl
openalex +6 more sources
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
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