About: Triangle-free graph

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Triangle-free graph Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Unit108189659, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FTriangle-free_graph

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.

Attributes	Values
rdf:type	software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659
rdfs:label	Grafos sin triángulos (es) Graphe sans triangle (fr) Граф без треугольников (ru) Grafos sem triangulos (pt) Triangle-free graph (en) Граф без трикутників (uk)
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)
foaf:depiction
dcterms:subject	Graph families
Wikipage page ID	7667996 (xsd:integer)
Wikipage revision ID	1102259533 (xsd:integer)
Link from a Wikipage to another Wikipage	Mycielskian Dense graph Graph families Regular graph Independent set (graph theory) Induced path Complete bipartite graph Mathematics Matrix multiplication Maximal independent set Median graph Neighbourhood (graph theory) Quantum algorithm Chromatic number Girth (graph theory) Graph coloring SIAM Journal on Computing SIAM Journal on Discrete Mathematics Andrásfai graph Clique (graph theory) Trace (linear algebra) Adjacency matrix Discrete Mathematics (journal) Graph theory Grötzsch's theorem Advances in Mathematics Bipartite graph Blanche Descartes Henson graph The American Mathematical Monthly Pigeonhole principle Planar graph Grötzsch graph Kneser graph Ramsey number Eureka (University of Cambridge magazine) Turán's theorem Ruzsa–Szemerédi problem Monochromatic triangle Triangle graph Shift graph Tutte Query complexity Decision tree complexity Journal of Combinatorial Theory, Series B
Link from a Wikipage to an external page	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
sameAs	Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph Triangle-free graph
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 49 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software