Results 11 to 20 of about 331 (182)
Hadwiger's Conjecture with Certain Forbidden Induced Subgraphs [PDF]
Experimental Mathematics, 2022 We prove that $\{\overline{K_3}, H\}$-free graphs are not counterexamples to Hadwiger's Conjecture, where $H$ is any one of 33 graphs on seven, eight, or nine vertices, or $H=K_8$. This improves on past results of Plummer-Stiebitz-Toft, Kriesell, and Bosse. The proofs are mostly computer-assisted.
Daniel Carter
openalex +3 more sources
On coloring digraphs with forbidden induced subgraphs [PDF]
Journal of Graph Theory, 2022 AbstractWe prove a conjecture by Aboulker, Charbit, and Naserasr by showing that every oriented graph in which the out‐neighborhood of every vertex induces a transitive tournament can be partitioned into two acyclic induced subdigraphs. We prove multiple extensions of this result to larger classes of digraphs defined by a finite list of forbidden ...
Raphael Steiner
openalex +4 more sources
Forbidden Induced Subgraphs [PDF]
Electronic Notes in Discrete Mathematics, 2017 In descending generality I survey: five partial orderings of graphs, the induced-subgraph ordering, and examples like perfect, threshold, and mock threshold graphs. The emphasis is on how the induced subgraph ordering differs from other popular orderings and leads to different basic questions.
Thomas Zasĺavsky
+7 more sources
Large homogeneous subgraphs in bipartite graphs with forbidden induced\n subgraphs [PDF]
Journal of Graph Theory, 2019 AbstractFor a bipartite graph , let be the largest such that either contains , a complete bipartite subgraph with parts of size , or the bipartite complement of contains as a subgraph. For a class of graphs , let . We say that a bipartite graph is strongly acyclic if neither nor its bipartite complement contains a cycle. By we denote the set of
Maria Axenovich +2 more
+8 more sources
Characterizing path graphs by forbidden induced subgraphs [PDF]
Journal of Graph Theory, 2009 AbstractA path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009 Wiley Periodicals, Inc.
Benjamin Lévêque +2 more
+7 more sources
The largest subgraph without a forbidden induced subgraph [PDF]
Combinatorica20 ...
Jacob Fox, Rajko Nenadov, Huy Tuan Pham
openalex +3 more sources
Hitting forbidden induced subgraphs on bounded treewidth graphs [PDF]
Information and Computation, 2021 For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus S$ does not contain $H$ as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph $H$
Ignasi Sau, Uéverton S. Souza
openalex +6 more sources
Forbidden Induced Subgraphs of Double-split Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2012 16 pages, 2 ...
Boris Alexeev +2 more
openalex +4 more sources
Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams [PDF]
, 2018 We propose a general method performed over multivalued decision diagrams that enumerates all subgraphs of an input graph that are characterized by input forbidden induced subgraphs. Our method combines elaborations of classical set operations and the developing construction technique, called the frontier based search, for multivalued decision diagrams.
Jun Kawahara +3 more
openalex +3 more sources
On Forbidden Induced Subgraphs for Unit Disk Graphs [PDF]
Discrete & Computational Geometry, 2018 A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit disk graphs very little is known about minimal forbidden induced subgraphs for this class. We found
Aistis Atminas, Viktor Zamaraev
openalex +5 more sources