Generalized matrix graphs and completely independent critical cliques in any dimension

John J. Lattanzio; Quan Zheng

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 583-602
  • ISSN: 2083-5892

Abstract

top
For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.

How to cite

top

John J. Lattanzio, and Quan Zheng. "Generalized matrix graphs and completely independent critical cliques in any dimension." Discussiones Mathematicae Graph Theory 32.3 (2012): 583-602. <http://eudml.org/doc/271081>.

@article{JohnJ2012,
abstract = {For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.},
author = {John J. Lattanzio, Quan Zheng},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {matrix graph; chromatic number; critical clique; completely independent critical cliques; double-critical conjecture; generalized matrix graph},
language = {eng},
number = {3},
pages = {583-602},
title = {Generalized matrix graphs and completely independent critical cliques in any dimension},
url = {http://eudml.org/doc/271081},
volume = {32},
year = {2012},
}

TY - JOUR
AU - John J. Lattanzio
AU - Quan Zheng
TI - Generalized matrix graphs and completely independent critical cliques in any dimension
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 583
EP - 602
AB - For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.
LA - eng
KW - matrix graph; chromatic number; critical clique; completely independent critical cliques; double-critical conjecture; generalized matrix graph
UR - http://eudml.org/doc/271081
ER -

References

top
  1. [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. Zbl1184.05039
  2. [2] R.A. Brualdi, Introductory Combinatorics, 5th ed, Pearson, (Upper Saddle River, 2010). 
  3. [3] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, 5th ed, CRC Press, (Boca Raton, 2010). 
  4. [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. [5] G.A. Dirac, The number of edges in critical graphs, J. Reine Angew. Math. 268/269 (1974) 150-164. Zbl0298.05119
  6. [6] P. Erdös, Problems, in: Theory of Graphs, Proc. Colloq., Tihany, (Academic Press, New York, 1968) 361-362. 
  7. [7] T.R. Jensen, Dense critical and vertex-critical graphs, Discrete Math. 258 (2002) 63-84, doi: 10.1016/S0012-365X(02)00262-5. Zbl1007.05048
  8. [8] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, 1995). 
  9. [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. Zbl1215.05069
  10. [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. Zbl0955.05042
  11. [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. Zbl0996.05046
  12. [12] J.J. Lattanzio, Completely independent critical cliques, J. Combin. Math. Combin. Comput. 62 (2007) 165-170. Zbl1137.05033
  13. [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. Zbl1227.05146
  14. [14] M. Stiebitz, K₅ is the only double-critical 5 -chromatic graph, Discrete Math. 64 (1987) 91-93, doi: 10.1016/0012-365X(87)90242-1. 
  15. [15] B. Toft, On the maximal number of edges of critical k -chromatic graphs, Studia Sci. Math. Hungar. 5 (1970) 461-470. Zbl0228.05111

NotesEmbed ?

top

You must be logged in to post comments.