The size of minimum 3-trees: cases 0 and 1 mod 12

Jorge L. Arocha; Joaquín Tey

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 177-187
  • ISSN: 2083-5892

Abstract

top
A 3-uniform hypergraph is called a minimum 3-tree, if for any 3-coloring of its vertex set there is a heterochromatic triple and the hypergraph has the minimum possible number of triples. There is a conjecture that the number of triples in such 3-tree is ⎡(n(n-2))/3⎤ for any number of vertices n. Here we give a proof of this conjecture for any n ≡ 0,1 mod 12.

How to cite

top

Jorge L. Arocha, and Joaquín Tey. "The size of minimum 3-trees: cases 0 and 1 mod 12." Discussiones Mathematicae Graph Theory 23.1 (2003): 177-187. <http://eudml.org/doc/270488>.

@article{JorgeL2003,
abstract = {A 3-uniform hypergraph is called a minimum 3-tree, if for any 3-coloring of its vertex set there is a heterochromatic triple and the hypergraph has the minimum possible number of triples. There is a conjecture that the number of triples in such 3-tree is ⎡(n(n-2))/3⎤ for any number of vertices n. Here we give a proof of this conjecture for any n ≡ 0,1 mod 12.},
author = {Jorge L. Arocha, Joaquín Tey},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {tight hypergraphs; triple systems; rainbow coloring; 3-uniform hypergraph},
language = {eng},
number = {1},
pages = {177-187},
title = {The size of minimum 3-trees: cases 0 and 1 mod 12},
url = {http://eudml.org/doc/270488},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Jorge L. Arocha
AU - Joaquín Tey
TI - The size of minimum 3-trees: cases 0 and 1 mod 12
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 177
EP - 187
AB - A 3-uniform hypergraph is called a minimum 3-tree, if for any 3-coloring of its vertex set there is a heterochromatic triple and the hypergraph has the minimum possible number of triples. There is a conjecture that the number of triples in such 3-tree is ⎡(n(n-2))/3⎤ for any number of vertices n. Here we give a proof of this conjecture for any n ≡ 0,1 mod 12.
LA - eng
KW - tight hypergraphs; triple systems; rainbow coloring; 3-uniform hypergraph
UR - http://eudml.org/doc/270488
ER -

References

top
  1. [1] J.L. Arocha, J. Bracho and V. Neumann-Lara, On the minimum size of tight hypergraphs, J. Graph Theory 16 (1992) 319-326, doi: 10.1002/jgt.3190160405. Zbl0776.05079
  2. [2] J.L. Arocha and J. Tey, The size of minimum 3-trees: Cases 3 and 4 mod 6, J. Graph Theory 30 (1999) 157-166, doi: 10.1002/(SICI)1097-0118(199903)30:3<157::AID-JGT1>3.0.CO;2-S Zbl0917.05053
  3. [3] J.L. Arocha and J. Tey, The size of minimum 3-trees: Case 2 mod 3, Bol. Soc. Mat. Mexicana (3) 8 no. 1 (2002) 1-4. Zbl1006.05011
  4. [4] L. Lovász, Topological and algebraic methods in graph theory, in: Graph Theory and Related Topics, Proceedings of Conference in Honour of W.T. Tutte, Waterloo, Ontario 1977, (Academic Press, New York, 1979) 1-14. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.