Concept

Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs. Trivially perfect graphs have several other equivalent characterizations: They are the comparability graphs of order-theoretic trees. That is, let T be a partial order such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation

Official source

https://en.wikipedia.org/wiki/Trivially_perfect_graph

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (1)

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

Related lectures (31)

Automorphism groups of trees and graphs II

Explores the uniqueness of trees, automorphism groups, Cayley-Abels graphs, and constructing vertex-transitive subgroups with prescribed local actions.

Graph Theory and Network Flows

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Statistical Analysis of Network Data

Introduces network data structures, models, and analysis techniques, emphasizing permutation invariance and Erdős-Rényi networks.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Official source

https://en.wikipedia.org/wiki/Trivially_perfect_graph

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (1)

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

Related lectures (31)

Automorphism groups of trees and graphs II

Explores the uniqueness of trees, automorphism groups, Cayley-Abels graphs, and constructing vertex-transitive subgroups with prescribed local actions.

Graph Theory and Network Flows

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Statistical Analysis of Network Data

Introduces network data structures, models, and analysis techniques, emphasizing permutation invariance and Erdős-Rényi networks.

Related publications (26)

Clique density vs blowups

A well-known theorem of Nikiforov asserts that any graph with a positive

K_{r}

-density contains a logarithmic blowup of

K_r

. In this paper, we explore variants of Nikiforov’s result in the following form. Given

r,t\in \mathbb{N}

, when a positive

K_{r}

-density implies the existence of a significantly larger (with almost linear size) blowup of

K_t

? Our results include: • For an

n

-vertex ordered graph

G

with no induced monotone path

P_{6}

, if its complement

\overline {G}

has positive t

Cambridge University Press (CUP)2026

Small-world scale-free brain networks from EEG with application to motor imagery decoding and brain fingerprinting

Developing individualized spatial models that capture the complex dynamics of multi-electrode EEG data is essential for accurately decoding global neural activity. A widely used approach is network modeling, where electrodes are represented as nodes. A key challenge lies in defining the network edges and weights, as precise connectivity estimation is critical for enhancing neural characterization and extracting discriminative features, such as those needed for task decoding. Traditional EEG-derived brain gr

2026

Automatic Speech Recognition and Acoustic Analysis for Dysarthria Assessment in Telerehabilitation: User-Centered Design and Usability Study

Background: Dysarthria is a frequent motor speech disorder following a stroke, affecting up to 42% of survivors and resulting in reduced speech intelligibility and diminished quality of life. Clinical assessments, such as the Frenchay Dysarthria Assessment, Second Edition (FDA-2), rely heavily on the subjective judgment of speech-language pathologists (SLPs), which limits comparability and scalability. Telepractice solutions have the potential to extend access to care, but validated digital tools that combi

2026

Related people (3)

Robert Dalang

Robert Dalang, né en 1961, a reçu le diplôme de Mathématicien-EPFL en 1983 et est lauréat du Prix Dommer. Il passe l'année 1985-86 à Cornell University (USA) comme chercheur invité. Il obtient le doctorat au Département de mathématiques de l'EPFL en 1987. Son domaine de spécialisation est la théorie des processeurs stochastiques. En 1987, Robert Dalang est nommé professeur assistant au Département de statistiques de l'Université de Californie à Berkeley (USA). En 1988, il reçoit une bourse post-doctorale du Fonds national scientifique américain et effectue des recherches sur les propriétés markoviennes de processus stochastiques à plusieurs paramètres. En 1990, il est nommé à Tufts University (Boston, USA). Il est promu professeur associé en mai 1993. Une partie importante de ses recherches se font dans le cadre de contrats avec le Fonds national scientifique américain et l'Office de la recherche de l'armée américaine. En collaboration avec le Prof. R. Cairoli du Département de mathématiques de l'EPFL, il a écrit un livre sur l'optimisation stochastique séquentielle publié en 1996 aux éditions John Wiley. M. Dalang est nommé professeur extraordinaire de probabilités au Département de mathématiques en 1995. Il y poursuit des travaux de recherche en processus stochastiques et probabilité appliquée et participe à l'enseignement des processus stochastiques, de la théorie des probabilités et des cours de mathématiques aux sections d'ingénieurs. Il dirige régulièrement des thèses de doctorats, est éditeur de plusieurs journaux de recherche mathématique et travail en collaboration avec des chercheurs de plusieurs universités européennes et américaines.

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Pierre Vandergheynst

Pierre Vandergheynst received the M.S. degree in physics and the Ph.D. degree in mathematical physics from the Université catholique de Louvain, Louvain-la-Neuve, Belgium, in 1995 and 1998, respectively. From 1998 to 2001, he was a Postdoctoral Researcher with the Signal Processing Laboratory, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He was Assistant Professor at EPFL (2002-2007), where he is now a Full Professor of Electrical Engineering and, by courtesy, of Computer and Communication Sciences. As of 2015, Prof. Vandergheynst serves as EPFL’s Vice-Provost for Education. His research focuses on harmonic analysis, sparse approximations and mathematical data processing in general with applications covering signal, image and high dimensional data processing, computer vision, machine learning, data science and graph-based data processing. He was co-Editor-in-Chief of Signal Processing (2002-2006), Associate Editor of the IEEE Transactions on Signal Processing (2007-2011), the flagship journal of the signal processing community and currently serves as Associate Editor of Computer Vision and Image Understanding and SIAM Imaging Sciences. He has been on the Technical Committee of various conferences, serves on the steering committee of the SPARS workshop and was co-General Chairman of the EUSIPCO 2008 conference. Pierre Vandergheynst is the author or co-author of more than 70 journal papers, one monograph and several book chapters. He has received two IEEE best paper awards. Professor Vandergheynst is a laureate of the Apple 2007 ARTS award and of the 2009-2010 De Boelpaepe prize of the Royal Academy of Sciences of Belgium.

Related units (1)

Transportation and Mobility Laboratory

Related concepts (12)

Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: Addition of a single isolated vertex to the graph. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices. For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.

Permutation graph

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition.

Universal vertex

In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused with a universally quantified vertex in the logic of graphs.) A graph that contains a universal vertex may be called a cone. In this context, the universal vertex may also be called the apex of the cone.

Related exercises (1)

Elliptical trajectory

A material point of mass m is moving in the plane defined by the orthonormal coordinate system Oxy such that its position vector is given by r⃗u2004=u2004Acosu2006(ωt)u2006îu2005+u2005Bsinu2006(ωt)u2006ĵ where A, B and ω are positive constants and î and ĵ are the unitary vectors of axes Ox and Oy.

Show that the material point’s path is elliptical. Sketch the velocity v⃗ and acceleration a⃗ vectors along the trajectory. Show that if Au2004≠u2004B, then vectors r⃗(t) and v⃗(t) are, generally,

Related notebooks (1)

Estimation of Electron Density and Mean Free Time for Transparent Conductors

Chapter 1: Transparent Conductors[1]¶ Instruction: The purpose of this notebook is to try and find values of electron density and mean free time for a material suitable to be used as a transparent conductors. The final estimate should be the order of the two parameters to be used[2]¶ In [1]: import numpy as np from bokeh.io import push_notebook, output_notebook, show from bokeh.layouts import row, column from bokeh.plotting import figure output_notebook() from ipywidgets import interact from collect

Related publications (26)