Search tip: add tags and a query to focus your search

By
kintali
on
Nov. 15, 2012
| Updated
on
May 19, 2013

A **perfect graph** is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.

Prove that bipartite graphs are perfect. Prove that the line graphs of bipartite graphs are perfect.

A graph is

**chordal**if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. Prove that chordal graphs are perfect.An

**interval graph**is the intersection graph of a multiset of intervals on the real line. Prove that interval graphs are chordal graphs and hence perfect.**Comparability graphs**are formed from partially ordered sets by connecting pairs of elements by an edge whenever they are related in the partial order. Prove that comparability graphs are perfect.$G$ has a clique $K$ such that $G − K$ has two components whose vertex sets are $A$, $B$. The subgraphs induced by $A \cup K$ and by $B \cup K$ are both perfect. Prove that $G$ is perfect.

[debug] activity: 156.0

By
trueshelf
on
Sept. 28, 2013
| Updated
on
Sept. 28, 2013

By
kintali
on
July 11, 2012
| Updated
on
Aug. 12, 2012

x ### Select What You'd Like To Post

TrueShelf is a unique educational website that focuses on crowdsourcing exercises and puzzles in Mathematics and Computer Science from high school level to graduate level.

© 2013 TrueShelf Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.