PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 3 | 583-602
Tytuł artykułu

Generalized matrix graphs and completely independent critical cliques in any dimension

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
32
Numer
3
Strony
583-602
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-02-14
poprawiono
2011-10-09
zaakceptowano
2011-10-15
Twórcy
  • Department of Mathematics, Indiana University of Pennsylvania, Indiana, PA 15705, USA
autor
  • Department of Mathematics, Indiana University of Pennsylvania, Indiana, PA 15705, USA
Bibliografia
  • [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, K₅ is the only double-critical 5 -chromatic graph, Discrete Math. 64 (1987) 91-93, doi: 10.1016/0012-365X(87)90242-1.
  • [15] B. Toft, On the maximal number of edges of critical k -chromatic graphs, Studia Sci. Math. Hungar. 5 (1970) 461-470.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1627
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.