Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650669 | Discrete Mathematics | 2008 | 15 Pages |
Abstract
A graph is called normal if its vertex set can be covered by cliques Q1,Q2,…,QkQ1,Q2,…,Qk and also by stable sets S1,S2,…,SlS1,S2,…,Sl, such that Si∩Qj≠∅Si∩Qj≠∅ for every i,ji,j. This notion is due to Körner, who introduced the class of normal graphs as an extension of the class of perfect graphs. Normality has also relevance in information theory. Here we prove, that the line graphs of cubic graphs are normal.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zsolt Patakfalvi,