Zsolt Patakfalvi
Published 2006-05-21Version 1
A graph is called normal if its vertex set can be covered by cliques and also by stable sets, such that every such clique and stable set have non-empty intersection. This notion is due to Korner, 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.
Comments: 16 pages, 10 figures
Journal: Discrete Mathematics 308 (2008) 2351--2365
On measures of edge-uncolorability of cubic graphs: A brief survey and some new results
The Sum and Product of Independence Numbers of Graphs and their Line Graphs
Delay colourings of cubic graphs
![QR code for arXiv:math/0605568 [math.CO]](http://oss.arxitics.com/images/favicon.svg)