Triangle-free graph (original) (raw)
En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle.
| Property | Value |
|---|---|
| dbo:abstract | En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle. (fr) En Teoría de grafos, un grafo sin triángulos es un grafo no dirigido en el que no existen tres vértices que formen un triángulo de aristas. Grafos sin triángulos pueden ser equivalentemente definidos como grafos con número de clique <= 2, grafos con cintura >= 4, grafos sin ciclos de tamaño 3, o grafos localmente independientes. Por el teorema de Turán, el grafo sin triángulos de N-vértice con el máximo número de aristas es un grafo bipartito completo en el que la cantidad de vértices en cada bipartición sea lo más similar posible. (es) In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible. (en) Na área de Teoria dos grafos da matemática, um grafo sem triângulos ou grafo livre de triângulos é um grafo não-direcionado no qual nenhum conjunto de três vértices forma um de arestas. Grafos sem triângulos podem ser equivalententemente definidos como grafos com clique ≤ 2, grafos com cintura ≥ 4, grafos sem , ou grafos localmente independentes. Pelo , um grafo sem triângulos de n-vertíces com o número máximo de arestas é um grafo bipartido completo em que o número de vértices em cada lado da bipartição é o mais semelhante possível. (pt) В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы. По теореме Турана граф с n вершинами, не имеющий треугольников, с максимальным числом рёбер является полным двудольным графом, в котором число вершин в каждой доле графа близки настолько, насколько возможно. В графе с 2n вершинами, не имеющем треугольников, должно быть меньше рёбер. (ru) У теорії графів графом без трикутників називається неорієнтований граф, в якому ніякі три вершини не утворюють трикутний граф з ребер. Графи без трикутників можна визначити також як графи з кліковим числом ≤ 2, графи з обхватом ≥ 4, графи без породжених 3-циклів, або локально незалежні графи. За теоремою Турана граф з n вершинами, що не має трикутників, з максимальним числом ребер є повним двочастковим графом, в якому числа вершин у кожній частці графа близькі настільки, наскільки можливо. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Biclique_K_5_5.svg?width=300 |
| dbo:wikiPageExternalLink | http://perso.ens-lyon.fr/stephan.thomasse/liste/vega11.pdf%7C http://real.mtak.hu/110445/1/1974-18.pdf https://www.sciencedirect.com/science/article/pii/S0304020808735527 http://dl.acm.org/citation.cfm%3Fid=2627817.2627924 https://semanticscholar.org/paper/26af19642d02045197c6b5a47a0691ea475ab747 https://semanticscholar.org/paper/600ab20562557a44611ef16b021aaf918002d672 http://www.graphclasses.org/classes/gc_371.html https://semanticscholar.org/paper/0d19245a27bc65a87a8014d5b8a66fb514c8ff0b |
| dbo:wikiPageID | 7667996 (xsd:integer) |
| dbo:wikiPageLength | 18275 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102259533 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mycielskian dbr:Dense_graph dbc:Graph_families dbr:Regular_graph dbr:Independent_set_(graph_theory) dbr:Induced_path dbr:Complete_bipartite_graph dbr:Mathematics dbr:Matrix_multiplication dbr:Maximal_independent_set dbr:Median_graph dbr:Neighbourhood_(graph_theory) dbr:Quantum_algorithm dbr:Chromatic_number dbr:Girth_(graph_theory) dbr:Graph_coloring dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Andrásfai_graph dbr:Clique_(graph_theory) dbr:Trace_(linear_algebra) dbr:Adjacency_matrix dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Grötzsch's_theorem dbr:Advances_in_Mathematics dbr:Bipartite_graph dbr:Blanche_Descartes dbr:Henson_graph dbr:The_American_Mathematical_Monthly dbr:Pigeonhole_principle dbr:Planar_graph dbr:Grötzsch_graph dbr:Kneser_graph dbr:Ramsey_number dbr:Eureka_(University_of_Cambridge_magazine) dbr:Turán's_theorem dbr:Ruzsa–Szemerédi_problem dbr:Monochromatic_triangle dbr:Triangle_graph dbr:Shift_graph dbr:Tutte dbr:Query_complexity dbr:Decision_tree_complexity dbr:Journal_of_Combinatorial_Theory,_Series_B dbr:File:Biclique_K_5_5.svg dbr:File:Groetzsch_graph_4COL.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sup |
| dct:subject | dbc:Graph_families |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle. (fr) En Teoría de grafos, un grafo sin triángulos es un grafo no dirigido en el que no existen tres vértices que formen un triángulo de aristas. Grafos sin triángulos pueden ser equivalentemente definidos como grafos con número de clique <= 2, grafos con cintura >= 4, grafos sin ciclos de tamaño 3, o grafos localmente independientes. Por el teorema de Turán, el grafo sin triángulos de N-vértice con el máximo número de aristas es un grafo bipartito completo en el que la cantidad de vértices en cada bipartición sea lo más similar posible. (es) In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible. (en) Na área de Teoria dos grafos da matemática, um grafo sem triângulos ou grafo livre de triângulos é um grafo não-direcionado no qual nenhum conjunto de três vértices forma um de arestas. Grafos sem triângulos podem ser equivalententemente definidos como grafos com clique ≤ 2, grafos com cintura ≥ 4, grafos sem , ou grafos localmente independentes. Pelo , um grafo sem triângulos de n-vertíces com o número máximo de arestas é um grafo bipartido completo em que o número de vértices em cada lado da bipartição é o mais semelhante possível. (pt) В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы. По теореме Турана граф с n вершинами, не имеющий треугольников, с максимальным числом рёбер является полным двудольным графом, в котором число вершин в каждой доле графа близки настолько, насколько возможно. В графе с 2n вершинами, не имеющем треугольников, должно быть меньше рёбер. (ru) У теорії графів графом без трикутників називається неорієнтований граф, в якому ніякі три вершини не утворюють трикутний граф з ребер. Графи без трикутників можна визначити також як графи з кліковим числом ≤ 2, графи з обхватом ≥ 4, графи без породжених 3-циклів, або локально незалежні графи. За теоремою Турана граф з n вершинами, що не має трикутників, з максимальним числом ребер є повним двочастковим графом, в якому числа вершин у кожній частці графа близькі настільки, наскільки можливо. (uk) |
| rdfs:label | Grafos sin triángulos (es) Graphe sans triangle (fr) Граф без треугольников (ru) Grafos sem triangulos (pt) Triangle-free graph (en) Граф без трикутників (uk) |
| owl:sameAs | freebase:Triangle-free graph yago-res:Triangle-free graph wikidata:Triangle-free graph dbpedia-es:Triangle-free graph dbpedia-fa:Triangle-free graph dbpedia-fr:Triangle-free graph dbpedia-hu:Triangle-free graph dbpedia-pt:Triangle-free graph dbpedia-ru:Triangle-free graph dbpedia-uk:Triangle-free graph https://global.dbpedia.org/id/4wMZ4 |
| prov:wasDerivedFrom | wikipedia-en:Triangle-free_graph?oldid=1102259533&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Biclique_K_5_5.svg wiki-commons:Special:FilePath/Groetzsch_graph_4COL.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Triangle-free_graph |
| is dbo:wikiPageRedirects of | dbr:Triangle-free dbr:Triangle_finding_problem |
| is dbo:wikiPageWikiLink of | dbr:Moser_spindle dbr:Mycielskian dbr:Cycle_(graph_theory) dbr:Cycle_double_cover dbr:Unit_distance_graph dbr:Induced_path dbr:Intersection_number_(graph_theory) dbr:Interval_edge_coloring dbr:Jan_Mycielski dbr:Penny_graph dbr:Complete_bipartite_graph dbr:Maximal_independent_set dbr:Median_graph dbr:Neighbourhood_(graph_theory) dbr:Zdeněk_Dvořák dbr:Clique_problem dbr:Friendship_graph dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Andrew_M._Gleason dbr:Andrásfai_graph dbr:Apex_graph dbr:Chordal_bipartite_graph dbr:Claw-free_graph dbr:Clebsch_graph dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Combinatorics dbr:Complement_graph dbr:Franklin_graph dbr:Halin_graph dbr:Harries–Wong_graph dbr:Butterfly_graph dbr:Václav_Chvátal dbr:Wagner_graph dbr:List_coloring dbr:Locally_linear_graph dbr:Three_utilities_problem dbr:Edge_coloring dbr:Forbidden_graph_characterization dbr:Brinkmann_graph dbr:Brooks'_theorem dbr:Outerplanar_graph dbr:Chvátal_graph dbr:Folded_cube_graph dbr:Four_color_theorem dbr:Graph_property dbr:Grötzsch's_theorem dbr:Hajós_construction dbr:Harries_graph dbr:Interval_graph dbr:Squaregraph dbr:Arrangement_of_lines dbr:Bidiakis_cube dbr:Henson_graph dbr:Herbert_Grötzsch dbr:Toroidal_graph dbr:Diamond_graph dbr:Distance-hereditary_graph dbr:Bull_graph dbr:Circle_graph dbr:Grötzsch_graph dbr:Implicit_graph dbr:Caterpillar_tree dbr:Rainbow-independent_set dbr:Rainbow_matching dbr:Ramsey's_theorem dbr:Strongly_regular_graph dbr:Simplex_graph dbr:Schläfli_graph dbr:Turán's_theorem dbr:Ruzsa–Szemerédi_problem dbr:Gewirtz_graph dbr:Monochromatic_triangle dbr:Second_neighborhood_problem dbr:Walk-regular_graph dbr:Triangle_graph dbr:Perfect_graph_theorem dbr:Shift_graph dbr:Χ-bounded dbr:Property_testing dbr:Scheinerman's_conjecture dbr:Subcoloring dbr:Triangle-free dbr:Triangle_finding_problem |
| is dbp:properties of | dbr:Andrásfai_graph dbr:Franklin_graph dbr:Harries–Wong_graph dbr:Wagner_graph dbr:Chvátal_graph dbr:Harries_graph dbr:Bidiakis_cube dbr:Grötzsch_graph dbr:Gewirtz_graph |
| is foaf:primaryTopic of | wikipedia-en:Triangle-free_graph |
