Relevant bibliographies by topics / Forbidden subgraph / Journal articles
To see the other types of publications on this topic, follow the link: Forbidden subgraph.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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
11

Li, Binlong, Hajo Broersma, and Shenggui Zhang. "Forbidden subgraph pairs for traceability of block-chains." Electronic Journal of Graph Theory and Applications 1, no. 1 (April 30, 2013): 1–10. http://dx.doi.org/10.5614/ejgta.2013.1.1.1.

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

Bonomo, Flavia, Guillermo Durán, Martín D. Safe, and Annegret K. Wagler. "On minimal forbidden subgraph characterizations of balanced graphs." Electronic Notes in Discrete Mathematics 35 (December 2009): 41–46. http://dx.doi.org/10.1016/j.endm.2009.11.008.

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

Panda, B. S. "The forbidden subgraph characterization of directed vertex graphs." Discrete Mathematics 196, no. 1-3 (February 1999): 239–56. http://dx.doi.org/10.1016/s0012-365x(98)00127-7.

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

Aravind, N. R., and C. R. Subramanian. "Forbidden subgraph colorings and the oriented chromatic number." European Journal of Combinatorics 34, no. 3 (April 2013): 620–31. http://dx.doi.org/10.1016/j.ejc.2011.09.045.

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

Bonomo, Flavia, Guillermo Durán, Martín D. Safe, and Annegret K. Wagler. "On minimal forbidden subgraph characterizations of balanced graphs." Discrete Applied Mathematics 161, no. 13-14 (September 2013): 1925–42. http://dx.doi.org/10.1016/j.dam.2013.04.001.

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

Desrosiers, Christian, Philippe Galinier, Pierre Hansen, and Alain Hertz. "Automated generation of conjectures on forbidden subgraph characterization." Discrete Applied Mathematics 162 (January 2014): 177–94. http://dx.doi.org/10.1016/j.dam.2013.07.013.

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

Ando, Kiyoshi. "A new forbidden subgraph for 5-contractible edges." Discrete Mathematics 343, no. 8 (August 2020): 111928. http://dx.doi.org/10.1016/j.disc.2020.111928.

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

Ashari, Yeva Fadhilah, A. N. M. Salman, and Rinovia Simanjuntak. "On Forbidden Subgraphs of (K2, H)-Sim-(Super)Magic Graphs." Symmetry 13, no. 8 (July 26, 2021): 1346. http://dx.doi.org/10.3390/sym13081346.

Full text
Abstract:
A graph G admits an H-covering if every edge of G belongs to a subgraph isomorphic to a given graph H. G is said to be H-magic if there exists a bijection f:V(G)∪E(G)→{1,2,…,|V(G)|+|E(G)|} such that wf(H′)=∑v∈V(H′)f(v)+∑e∈E(H′)f(e) is a constant, for every subgraph H′ isomorphic to H. In particular, G is said to be H-supermagic if f(V(G))={1,2,…,|V(G)|}. When H is isomorphic to a complete graph K2, an H-(super)magic labeling is an edge-(super)magic labeling. Suppose that G admits an F-covering and H-covering for two given graphs F and H. We define G to be (F,H)-sim-(super)magic if there exists a bijection f′ that is simultaneously F-(super)magic and H-(super)magic. In this paper, we consider (K2,H)-sim-(super)magic where H is isomorphic to three classes of graphs with varied symmetry: a cycle which is symmetric (both vertex-transitive and edge-transitive), a star which is edge-transitive but not vertex-transitive, and a path which is neither vertex-transitive nor edge-transitive. We discover forbidden subgraphs for the existence of (K2,H)-sim-(super)magic graphs and classify classes of (K2,H)-sim-(super)magic graphs. We also derive sufficient conditions for edge-(super)magic graphs to be (K2,H)-sim-(super)magic and utilize such conditions to characterize some (K2,H)-sim-(super)magic graphs.
APA, Harvard, Vancouver, ISO, and other styles
19

LOZIN, VADIM V., and JORDAN VOLZ. "THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES." International Journal of Foundations of Computer Science 19, no. 02 (April 2008): 477–94. http://dx.doi.org/10.1142/s0129054108005772.

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

FUJITA, SHINYA, MICHITAKA FURUYA, and KENTA OZEKI. "Forbidden Subgraphs Generating Almost the Same Sets." Combinatorics, Probability and Computing 22, no. 5 (July 11, 2013): 733–48. http://dx.doi.org/10.1017/s0963548313000254.

Full text
Abstract:
Let $\mathcal{H}$ be a set of connected graphs. A graph G is said to be $\mathcal{H}$-free if G does not contain any element of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{F}_{k}(\mathcal{H})$ be the set of k-connected $\mathcal{H}$-free graphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow a finite exceptional set of graphs. But if the symmetric difference of $\mathcal{F}_{k}(\mathcal{H}_{1})$ and $\mathcal{F}_{k}(\mathcal{H}_{2})$ is finite and we allow a finite number of exceptions, no graph property can distinguish them. Motivated by this observation, we study when we obtain a finite symmetric difference. In this paper, our main aim is the following. If $|\mathcal{H}|\leq 3$ and the symmetric difference of $\mathcal{F}_{1}(\{H\})$ and $\mathcal{F}_{1}(\mathcal{H})$ is finite, then either $H\in \mathcal{H}$ or $|\mathcal{H}|=3$ and H=C3. Furthermore, we prove that if the symmetric difference of $\mathcal{F}_{k}(\{H_{1}\})$ and $\mathcal{F}_{k}(\{H_{2}\})$ is finite, then H1=H2.
APA, Harvard, Vancouver, ISO, and other styles
21

Cerioli, M. R., and P. Petito. "Forbidden subgraph characterization of split graphs that are UEH." Electronic Notes in Discrete Mathematics 19 (June 2005): 305–11. http://dx.doi.org/10.1016/j.endm.2005.05.041.

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

Couto, Fernanda, Luerbio Faria, Sylvain Gravier, and Sulamita Klein. "On the forbidden induced subgraph probe and sandwich problems." Discrete Applied Mathematics 234 (January 2018): 56–66. http://dx.doi.org/10.1016/j.dam.2016.04.005.

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

Cherlin, Gregory, and Saharon Shelah. "Universal graphs with a forbidden subgraph: Block path solidity." Combinatorica 36, no. 3 (May 25, 2015): 249–64. http://dx.doi.org/10.1007/s00493-014-3181-5.

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

Huang, Jing, and Baogang Xu. "A forbidden subgraph characterization of line-polar bipartite graphs." Discrete Applied Mathematics 158, no. 6 (March 2010): 666–80. http://dx.doi.org/10.1016/j.dam.2009.12.012.

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

Hu, Zhiquan, and Houyuan Lin. "Two Forbidden Subgraph Pairs for Hamiltonicity of 3-Connected Graphs." Graphs and Combinatorics 29, no. 6 (October 27, 2012): 1755–75. http://dx.doi.org/10.1007/s00373-012-1245-0.

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

Chen, Guantao, Jie Han, Suil O, Songling Shan, and Shoichi Tsuchiya. "Forbidden Pairs and the Existence of a Spanning Halin Subgraph." Graphs and Combinatorics 33, no. 5 (September 2017): 1321–45. http://dx.doi.org/10.1007/s00373-017-1847-7.

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

Lin, Hou-yuan, and Zhi-quan Hu. "Four forbidden subgraph pairs for hamiltonicity of 3-connected graphs." Acta Mathematicae Applicatae Sinica, English Series 32, no. 2 (April 29, 2016): 469–76. http://dx.doi.org/10.1007/s10255-016-0573-x.

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

Chen, Li-Hsuan, Ling-Ju Hung, Henri Lotze, and Peter Rossmanith. "Online Node- and Edge-Deletion Problems with Advice." Algorithmica 83, no. 9 (June 30, 2021): 2719–53. http://dx.doi.org/10.1007/s00453-021-00840-9.

Full text
Abstract:
AbstractIn online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class $$\Pi $$ Π at all times. We consider only hereditary properties $$\Pi $$ Π , for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs $${{\mathcal{F}}}$$ F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed Connected$${{\mathcal{F}}}$$ F -Node-Deletion Problem, where all graphs of the family $${\mathcal{F}}$$ F have to be connected and almost tight lower and upper bounds for the Delayed$$H$$ H -Node-Deletion Problem, where there is one forbidden induced subgraph H that may be connected or not. For the Delayed$$H$$ H -Node-Deletion Problem the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected$${\mathcal{F}}$$ F -Edge-Deletion Problem, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from $${\mathcal{F}}$$ F . We give a separate analysis for the Delayed Connected$$H$$ H -Edge-Deletion Problem, which is less general but admits a bound that is easier to compute.
APA, Harvard, Vancouver, ISO, and other styles
29

Kirmani, S. A. K., Merajuddin, and Parvez Ali. "On self-complementary chordal graphs defined by single forbidden induced subgraph." Applied Mathematical Sciences 8 (2014): 2655–63. http://dx.doi.org/10.12988/ams.2014.24281.

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

Hu, Zhiquan. "A generalization of fan's condition and forbidden subgraph conditions for hamiltonicity." Discrete Mathematics 196, no. 1-3 (February 1999): 167–75. http://dx.doi.org/10.1016/s0012-365x(98)00200-3.

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

Brandstädt, Andreas, Van Bang Le, and Dieter Rautenbach. "A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers." Discrete Mathematics 309, no. 12 (June 2009): 3843–52. http://dx.doi.org/10.1016/j.disc.2008.10.025.

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

Dantas, Simone, Celina M. H. de Figueiredo, Priscila Petito, and Rafael B. Teixeira. "A General Method for Forbidden Induced Subgraph Sandwich Problem NP-completeness." Electronic Notes in Theoretical Computer Science 346 (August 2019): 393–400. http://dx.doi.org/10.1016/j.entcs.2019.08.035.

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

Changat, Manoj, Anandavally K. Lakshmikuttyamma, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Geetha Seethakuttyamma, and Simon Špacapan. "A forbidden subgraph characterization of some graph classes using betweenness axioms." Discrete Mathematics 313, no. 8 (April 2013): 951–58. http://dx.doi.org/10.1016/j.disc.2013.01.013.

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

Cicerone, Serafino. "A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2." Algorithms 14, no. 4 (March 25, 2021): 105. http://dx.doi.org/10.3390/a14040105.

Full text
Abstract:
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 the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the k-distance-hereditary graphs such that k<2. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph.
APA, Harvard, Vancouver, ISO, and other styles
35

Samuel, Libin Chacko, and Mayamma Joseph. "New results on connected dominating structures in graphs." Acta Universitatis Sapientiae, Informatica 11, no. 1 (August 1, 2019): 52–64. http://dx.doi.org/10.2478/ausi-2019-0004.

Full text
Abstract:
Abstract A set of vertices in a graph is a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating structure is a subgraph induced by the dominating set. Connected domination is a type of domination where the dominating structure is connected. Clique domination is a type of domination in graphs where the dominating structure is a complete subgraph. The clique domination number of a graph G denoted by γk(G) is the minimum cardinality among all the clique dominating sets of G. We present few properties of graphs admitting dominating cliques along with bounds on clique domination number in terms of order and size of the graph. A necessary and sufficient condition for the existence of dominating clique in strong product of graphs is presented. A forbidden subgraph condition necessary to imply the existence of a connected dominating set of size four also is found.
APA, Harvard, Vancouver, ISO, and other styles
36

Palathingal, Jeepamol J., and Aparna Lakshmanan. S. "Forbidden Subgraph Characterizations of Extensions of Gallai Graph Operator to Signed Graph." Annals of Pure and Applied Mathematics 14, no. 3 (October 25, 2017): 437–48. http://dx.doi.org/10.22457/apam.v14n3a10.

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

ADIPRASITO, KARIM, ERAN NEVO, and MARTIN TANCER. "On Betti numbers of flag complexes with forbidden induced subgraphs." Mathematical Proceedings of the Cambridge Philosophical Society 168, no. 3 (June 7, 2019): 567–600. http://dx.doi.org/10.1017/s030500411900001x.

Full text
Abstract:
AbstractWe analyse the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H.In particular, we prove a theorem of the alternative: for any H the growth rate achieves exactly one of five possible exponentials, that is, independent of the field of coefficients, the nth root of the maximal total Betti number over n-vertex graphs with no induced copy of H has a limit, as n tends to infinity, and, ranging over all H, exactly five different limits are attained.For the interesting case where H is the 4-cycle, the above limit is 1, and we prove a superpolynomial upper bound.
APA, Harvard, Vancouver, ISO, and other styles
38

Durán, Guillermo. "Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey." Electronic Notes in Discrete Mathematics 44 (November 2013): 399–404. http://dx.doi.org/10.1016/j.endm.2013.10.062.

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

Ando, Kiyoshi, and Ken-ichi Kawarabayashi. "Some forbidden subgraph conditions for a graph to have a k-contractible edge." Discrete Mathematics 267, no. 1-3 (June 2003): 3–11. http://dx.doi.org/10.1016/s0012-365x(02)00598-8.

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

Dantas, Simone, Celina M. H. de Figueiredo, Frédéric Maffray, and Rafael B. Teixeira. "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem." Discrete Applied Mathematics 182 (February 2015): 15–24. http://dx.doi.org/10.1016/j.dam.2013.09.004.

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

McKee, Terry A. "Requiring adjacent chords in cycles." Discrete Mathematics, Algorithms and Applications 10, no. 01 (February 2018): 1850003. http://dx.doi.org/10.1142/s1793830918500039.

Full text
Abstract:
Define a new class of graphs by cycles of length 5 or more always having adjacent chords. This is equivalent to cycles of length 5 or more always having noncrossing chords, which is a property that has a known forbidden induced subgraph characterization. Another characterization comes from viewing the graphs in this class in contrast to distance-hereditary graphs (which are characterized by cycles of length 5 or more always having crossing chords). Moreover, the graphs in the new class are those in which every edge of every cycle [Formula: see text] of length 5 or more forms a triangle with a third vertex of [Formula: see text] (generalizing that a graph is chordal if and only if every edge of every cycle [Formula: see text] of length 4 or more forms a triangle with a third vertex of [Formula: see text]). This leads to a strategically-required subgraph characterization of the new class.
APA, Harvard, Vancouver, ISO, and other styles
42

Kumar, Mrinal, Sounaka Mishra, N. Safina Devi, and Saket Saurabh. "Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization." Theoretical Computer Science 526 (March 2014): 90–96. http://dx.doi.org/10.1016/j.tcs.2014.01.019.

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

Ando, Kiyoshi. "Some degree and forbidden subgraph conditions for a graph to have a k-contractible edge." Discrete Mathematics 339, no. 1 (January 2016): 207–16. http://dx.doi.org/10.1016/j.disc.2015.07.016.

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

Thomas, Robin. "A counter-example to ‘Wagner's conjecture’ for infinite graphs." Mathematical Proceedings of the Cambridge Philosophical Society 103, no. 1 (January 1988): 55–57. http://dx.doi.org/10.1017/s0305004100064616.

Full text
Abstract:
Wagner made the conjecture that given an infinite sequence G1, G2, … of finite graphs there are indices i < j such that Gi is a minor of Gj. (A graph is a minor of another if the first can be obtained by contraction from a subgraph of the second.) The importance of this conjecture is that it yields excluded minor theorems in graph theory, where by an excluded minor theorem we mean a result asserting that a graph possesses a specified property if and only if none of its minors belongs to a finite list of ‘forbidden minors’. A widely known example of an excluded minor theorem is Kuratowski's famous theorem on planar graphs; one of its formulations says that a graph is planar if and only if it has neither K5 nor K3, 3 as a minor. But several other excluded minor theorems have been discovered by now (see e.g. [7–9]).
APA, Harvard, Vancouver, ISO, and other styles
45

GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (September 2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.

Full text
Abstract:
In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.
APA, Harvard, Vancouver, ISO, and other styles
46

Cherlin, Gregory, and Niandong Shi. "Forbidden subgraphs and forbidden substructures." Journal of Symbolic Logic 66, no. 3 (September 2001): 1342–52. http://dx.doi.org/10.2307/2695110.

Full text
Abstract:
AbstractThe problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in the category of graphs with a vertex coloring by two colors. It is not known whether this problem reduces further to the category of ordinary graphs. It is also not known whether these problems are decidable.
APA, Harvard, Vancouver, ISO, and other styles
47

Zaslavsky, Thomas. "Forbidden Induced Subgraphs." Electronic Notes in Discrete Mathematics 63 (December 2017): 3–10. http://dx.doi.org/10.1016/j.endm.2017.10.056.

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

Caro, Yair, Juan Rojas, and Sergio Ruiz. "A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs." Czechoslovak Mathematical Journal 46, no. 3 (1996): 413–19. http://dx.doi.org/10.21136/cmj.1996.127306.

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

Fujita, Shinya. "Disjoint stars and forbidden subgraphs." Hiroshima Mathematical Journal 36, no. 3 (November 2006): 397–403. http://dx.doi.org/10.32917/hmj/1171377081.

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

Ravelomanana, Vlady, and Loÿs Thimonier. "Forbidden subgraphs in connected graphs." Theoretical Computer Science 314, no. 1-2 (February 2004): 121–71. http://dx.doi.org/10.1016/j.tcs.2003.11.024.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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