Discussiones Mathematicae Graph Theory 32(3) (2012)
583-602

doi: 10.7151/dmgt.1627

John J. Lattanzio and Quan Zheng
Department of Mathematics |

**Keywords:** matrix graph, chromatic number, critical clique, completely independent critical cliques, double-critical conjecture

**2010 Mathematics Subject Classification:** 05C15.

[1] | J. Balogh, A.V. Kostochka, N. Prince, and M. Stiebitz, The Erdös-Lovász Tihany conjecture for quasi-line graphs, Discrete Math., 309 (2009) 3985--3991, doi: 10.1016/j.disc.2008.11.016. |

[2] | R.A. Brualdi, Introductory Combinatorics, 5th ed, Pearson, (Upper Saddle River, 2010). |

[3] | G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, 5th ed, CRC Press, (Boca Raton, 2010). |

[4] | G.A. Dirac, A theorem of R.L. Brooks and a conjecture of H. Hadwiger, Proc. Lond. Math. Soc. (3), 7 (1957) 161--195, doi: 10.1112/plms/s3-7.1.161. |

[5] | G.A. Dirac, The number of edges in critical graphs, J. Reine Angew. Math. 268/269 (1974) 150--164. |

[6] | P. Erdös, Problems, in: Theory of Graphs, Proc. Colloq., Tihany, (Academic Press, New York, 1968) 361--362. |

[7] | T.R. Jensen, Dense critical and vertex-critical graphs, Discrete Math. 258 (2002) 63--84, doi: 10.1016/S0012-365X(02)00262-5. |

[8] | T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, 1995). |

[9] | K.-i. Kawarabayashi, A.S. Pedersen and B. Toft, Double-critical graphs and complete minors,Retrieved from http://adsabs.harvard.edu/abs/2008arXiv0810.3133K. |

[10] | A.V. Kostochka and M. Stiebitz, Colour-critical graphs with few edges, Discrete Math. 191 (1998) 125--137, doi: 10.1016/S0012-365X(98)00100-9. |

[11] | A.V. Kostochka and M. Stiebitz, On the number of edges in colour-critical graphs and hypergraphs, Combinatorica 20 (2000) 521--530, doi: 10.1007/s004930070005. |

[12] | J.J. Lattanzio, Completely independent critical cliques, J. Combin. Math. Combin. Comput. 62 (2007) 165--170. |

[13] | J.J. Lattanzio, Edge double-critical graphs, Journal of Mathematics and Statistics 6 (3) (2010) 357--358, doi: 10.3844/jmssp.2010.357.358. |

[14] | M. Stiebitz, , Discrete Math. K is the only double-critical _{5} 5 -chromatic graph 64 (1987) 91--93, doi: 10.1016/0012-365X(87)90242-1. |

[15] | B. Toft, On the maximal number of edges of critical , Studia Sci. Math. Hungar. k -chromatic graphs 5 (1970) 461--470. |

Received 14 February 2011

Revised 9 October 2011

Accepted 15 October 2011