Relevant bibliographies by topics / Forbidden subgraph

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Forbidden subgraph'

Author: Grafiati
Published: 4 June 2021
Last updated: 8 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Forbidden subgraph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Forbidden subgraph"

1

Rusu, Irena, and Jeremy Spinrad. "Forbidden subgraph decomposition." Discrete Mathematics 247, no. 1-3 (March 2002): 159–68. http://dx.doi.org/10.1016/s0012-365x(01)00173-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ginn, Mark. "Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes." Journal of Graph Theory 30, no. 2 (February 1999): 71–76. http://dx.doi.org/10.1002/(sici)1097-0118(199902)30:2<71::aid-jgt1>3.0.co;2-g.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Nikoghosyan, Zh G. "Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles." ISRN Combinatorics 2013 (March 10, 2013): 1–4. http://dx.doi.org/10.1155/2013/673971.

Full text
Abstract:
In 1974, Goodman and Hedetniemi proved that every 2-connected -free graph is hamiltonian. This result gave rise many other conditions for Hamilton cycles concerning various pairs and triples of forbidden connected subgraphs under additional connectivity conditions. In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures. In 1997, it was proved that a single forbidden connected subgraph in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with . In this paper we prove that a single forbidden subgraph can create a non trivial class of hamiltonian graphs if is disconnected: every -free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs; every 1-tough -free graph is hamiltonian. We conjecture that every 1-tough -free graph is hamiltonian and every 1-tough -free graph is hamiltonian.
APA, Harvard, Vancouver, ISO, and other styles
4

Zheng, Wei, Hajo Broersma, and Ligong Wang. "Toughness, Forbidden Subgraphs and Pancyclicity." Graphs and Combinatorics 37, no. 3 (February 19, 2021): 839–66. http://dx.doi.org/10.1007/s00373-021-02284-y.

Full text
Abstract:
AbstractMotivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of $$K_1\cup P_4$$ K 1 ∪ P 4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph $$K_1\cup P_4$$ K 1 ∪ P 4 itself. The hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs we give infinite families of graphs that are not pancyclic.
APA, Harvard, Vancouver, ISO, and other styles
5

Saito, Akira, and Liming Xiong. "The Ryjáček closure and a forbidden subgraph." Discussiones Mathematicae Graph Theory 36, no. 3 (2016): 621. http://dx.doi.org/10.7151/dmgt.1876.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Tondato, Silvia B., Marisa Gutierrez, and Jayme L. Szwarcfiter. "A forbidden subgraph characterization of path graphs." Electronic Notes in Discrete Mathematics 19 (June 2005): 281–87. http://dx.doi.org/10.1016/j.endm.2005.05.038.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Zverovich, Igor Ed, and Inessa I. Zverovich. "Forbidden induced subgraph characterization of cograph contractions." Journal of Graph Theory 46, no. 3 (April 7, 2004): 217–26. http://dx.doi.org/10.1002/jgt.20002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Golovach, Petr A., Daniël Paulusma, and Bernard Ries. "Coloring graphs characterized by a forbidden subgraph." Discrete Applied Mathematics 180 (January 2015): 101–10. http://dx.doi.org/10.1016/j.dam.2014.08.008.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Dantas, Simone, Celina M. H. de Figueiredo, Murilo V. G. da Silva, and Rafael B. Teixeira. "On the forbidden induced subgraph sandwich problem." Discrete Applied Mathematics 159, no. 16 (September 2011): 1717–25. http://dx.doi.org/10.1016/j.dam.2010.11.010.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

LOH, PO-SHEN, MICHAEL TAIT, CRAIG TIMMONS, and RODRIGO M. ZHOU. "Induced Turán Numbers." Combinatorics, Probability and Computing 27, no. 2 (November 2, 2017): 274–88. http://dx.doi.org/10.1017/s0963548317000542.

Full text
Abstract:
The classical Kővári–Sós–Turán theorem states that ifGis ann-vertex graph with no copy ofKs,tas a subgraph, then the number of edges inGis at mostO(n2−1/s). We prove that if one forbidsKs,tas aninducedsubgraph, and also forbidsanyfixed graphHas a (not necessarily induced) subgraph, the same asymptotic upper bound still holds, with different constant factors. This introduces a non-trivial angle from which to generalize Turán theory to induced forbidden subgraphs, which this paper explores. Along the way, we derive a non-trivial upper bound on the number of cliques of fixed order in aKr-free graph with no induced copy ofKs,t. This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Forbidden subgraph"

1

Barrus, Michael D. "A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes." BYU ScholarsArchive, 2004. https://scholarsarchive.byu.edu/etd/125.

Full text
Abstract:
The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.
APA, Harvard, Vancouver, ISO, and other styles
2

Barrus, Michael David. "A forbidden subgraph characterization problem and a minimal-element subset of universal graph classes /." Diss., CLICK HERE for online access, 2004. http://contentdm.lib.byu.edu/ETD/image/etd374.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Ye, Tianjun. "Forbidden subgraphs and 3-colorability." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/48986.

Full text
Abstract:
Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.
APA, Harvard, Vancouver, ISO, and other styles
4

Grout, Jason Nicholas. "The Minimum Rank Problem Over Finite Fields." Diss., CLICK HERE for online access, 2007. http://contentdm.lib.byu.edu/ETD/image/etd1995.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Altomare, Christian J. "Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1259546079.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Walker, DayVon L. "Power Graphs of Quasigroups." Scholar Commons, 2019. https://scholarcommons.usf.edu/etd/7984.

Full text
Abstract:
We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups (up to four elements). Next we describe quasigroups whose power graphs are directed paths, directed cycles, in-stars, out-stars, and empty. We do so by specifying partial Cayley tables, which cannot always be completed in small examples. We then consider sinks in the power graph of a quasigroup, as subquasigroups give rise to sinks. We show that certain structures cannot occur as sinks in the power graph of a quasigroup. More generally, we show that certain highly connected substructures must have edges leading out of the substructure. We briefly comment on power graphs of Bol loops.
APA, Harvard, Vancouver, ISO, and other styles
7

Genova, Daniela. "Forbidding and enforcing of formal languages, graphs, and partially ordered sets." [Tampa, Fla.] : University of South Florida, 2007. http://purl.fcla.edu/usf/dc/et/SFE0002102.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Yang, Ping. "Spanning Halin Subgraphs Involving Forbidden Subgraphs." 2016. http://scholarworks.gsu.edu/math_diss/29.

Full text
Abstract:
In structural graph theory, connectivity is an important notation with a lot of applications. Tutte, in 1961, showed that a simple graph is 3-connected if and only if it can be generated from a wheel graph by repeatedly adding edges between nonadjacent vertices and applying vertex splitting. In 1971, Halin constructed a class of edge-minimal 3-connected planar graphs, which are a generalization of wheel graphs and later were named “Halin graphs” by Lovasz and Plummer. A Halin graph is obtained from a plane embedding of a tree with no stems having degree 2 by adding a cycle through its leaves in the natural order determined according to the embedding. Since Halin graphs were introduced, many useful properties, such as Hamiltonian, hamiltonian-connected and pancyclic, have been discovered. Hence, it will reveal many properties of a graph if we know the graph contains a spanning Halin subgraph. But unfortunately, until now, there is no positive result showing under which conditions a graph contains a spanning Halin subgraph. In this thesis, we characterize all forbidden pairs implying graphs containing spanning Halin subgraphs. Consequently, we provide a complete proof conjecture of Chen et al. Our proofs are based on Chudnovsky and Seymour’s decomposition theorem of claw-free graphs, which were published recently in a series of papers.
APA, Harvard, Vancouver, ISO, and other styles
9

Doan, Trung Duy. "Proper connection number of graphs." Doctoral thesis, 2018. https://tubaf.qucosa.de/id/qucosa%3A31245.

Full text
Abstract:
The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph. The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6. Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation. In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs. In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.
APA, Harvard, Vancouver, ISO, and other styles
10

Berger, Amelie Julie. "Minimal reducible bounds, forbidden subgraphs and prime ideals in the lattice of additive hereditary graph properties." Thesis, 2012. http://hdl.handle.net/10210/4277.

Full text
Abstract:
Ph.D.
After giving basic definitions concerning additive hereditary properties of graphs, this document is divided into three main sections, concerning minimal reducible bounds, minimal forbidden subgraphs and prime ideals. We prove that every irreducible property has at least one minimal reducible bound, and that if an irreducible property P is contained in a reducible property R, then there is a minimal reducible bound for P contained in R. In addition we show that every reducible property serves as a minimal reducible bound for some irreducible property. Several applications of these results are given in the case of hom-properties, mainly to show the existence of minimal reducible bounds of certain types. We prove that every degenerate property has a minimal reducible bound where one factor is the class of edgeless graphs and provide evidence that this may also be true for an arbitrary irreducible property. We also consider edge partitions and we show that the results for minimal decomposable bounds are similar to those for minimal reducible bounds. The second set of results deals with minimal forbidden subgraphs of graph properties. We show that every reducible property has infinitely many minimal forbidden subgraphs since the set of all the cyclic blocks making up these graphs is infinite. Finally we consider the lattice of all additive hereditary properies and study the prime ideals in this lattice. We give an example of a prime ideal that is not co-principal and give some requirements that non co-principal prime ideals should satisfy. 'vVe prove that the set of properties with bounded chromatic number is not a prime ideal by showing that a property P with bounded chromatic number can be written as the intersection of two properties with unbounded chromatic number if and only if P contains all trees.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Forbidden subgraph"

1

Golovach, Petr A., Daniël Paulusma, and Bernard Ries. "Coloring Graphs Characterized by a Forbidden Subgraph." In Mathematical Foundations of Computer Science 2012, 443–54. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32589-2_40.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Aravind, N. R., and C. R. Subramanian. "Forbidden Subgraph Colorings and the Oriented Chromatic Number." In Lecture Notes in Computer Science, 60–71. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-10217-2_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Damaschke, P. "Forbidden Ordered Subgraphs." In Topics in Combinatorics and Graph Theory, 219–29. Heidelberg: Physica-Verlag HD, 1990. http://dx.doi.org/10.1007/978-3-642-46908-4_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Magnant, Colton, and Pouria Salehi Nowbandegani. "General Structure Under Forbidden Rainbow Subgraphs." In Topics in Gallai-Ramsey Theory, 9–23. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-48897-0_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Brandstädt, Andreas, Joost Engelfriet, Hoàng-Oanh Le, and Vadim V. Lozin. "Clique-Width for Four-Vertex Forbidden Subgraphs." In Fundamentals of Computation Theory, 185–96. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11537311_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Dabrowski, Konrad K., Petr A. Golovach, and Daniël Paulusma. "Colouring of Graphs with Ramsey-Type Forbidden Subgraphs." In Graph-Theoretic Concepts in Computer Science, 201–12. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-45043-3_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Das, Ashok Kumar, and Ritapa Chakraborty. "Forbidden Subgraphs of Bigraphs of Ferrers Dimension 2." In Theoretical Computer Science and Discrete Mathematics, 38–49. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-64419-6_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Cygan, Marek, Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. "Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth." In Mathematical Foundations of Computer Science 2014, 189–200. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44465-8_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Král’, Daniel, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. "Complexity of Coloring Graphs without Forbidden Induced Subgraphs." In Graph-Theoretic Concepts in Computer Science, 254–62. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45477-2_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Cai, Leizhen, and Chengwei Guo. "Contracting Few Edges to Remove Forbidden Induced Subgraphs." In Parameterized and Exact Computation, 97–109. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-03898-8_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Forbidden subgraph"

1

Yan, Jingzhi, Bin Hu, Heping Zhang, Tingzhao Zhu, and Xiaowei Li. "Forbidden subgraph and perfect path-matchings." In 2009 1st IEEE Symposium on Web Society (SWS). IEEE, 2009. http://dx.doi.org/10.1109/sws.2009.5271774.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Chudnovsky, Maria, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong. "Obstructions for three-coloring graphs with one forbidden induced subgraph." In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974331.ch123.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Chen, Yijia, and Jorg Flum. "Forbidden Induced Subgraphs and the Łoś–Tarski Theorem." In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2021. http://dx.doi.org/10.1109/lics52264.2021.9470742.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Applebaum, Benny, and Eliran Kachlon. "Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error." In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019. http://dx.doi.org/10.1109/focs.2019.00020.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Djidjev, Hristo, and John Reif. "An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs." In the twenty-third annual ACM symposium. New York, New York, USA: ACM Press, 1991. http://dx.doi.org/10.1145/103418.103456.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Czumaj, Artur, and Christian Sohler. "A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)." In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019. http://dx.doi.org/10.1109/focs.2019.00089.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Forbidden subgraph' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography