Premium
Extremal interval graphs
Author(s) -
Eckhoff Jürgen
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170112
Subject(s) - combinatorics , mathematics , indifference graph , interval (graph theory) , chordal graph , split graph , interval graph , discrete mathematics , clique number , clique sum , clique , cograph , block graph , pathwidth , graph , 1 planar graph , line graph
An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for the numbers of such graphs. © 1993 John Wiley & Sons, Inc.