On embedding degree sequences

Béla Csaba, Bálint Márk Vásárhelyi

Abstract


Assume that we are given two graphic sequences, $\pi_1$ and $\pi_2$. We consider conditions for $\pi_1$ and $\pi_2$ which guarantee that there exists a simple graph $G_2$ realizing $\pi_2$ such that $G_2$ is the subgraph of any simple graph $G_1$ that realizes $\pi_1$.

Full Text:

PDF

References


bibitem{AS} N.~Alon, J.~Spencer. {it The probabilistic method.} Third edition, John Wiley & Sons,

Inc., 2008.

bibitem{chvatal} V.~Chv'atal and E.~Szemer'edi. On the {E}rd{H o}s--{S}tone {T}heorem.

{em Journal of the London Mathematical Society}, s2-23 (2):207--214, 1981.

bibitem{corradi} K.~Corr'adi and A.~Hajnal. On the maximal number of independent circuits in a graph. {em Acta Mathematica Academiae Scientiarum Hungaricae}, 14:423--439, 1963.

bibitem{wellsep} B.~Csaba. On embedding well-separable graphs. {em Discrete Mathematics}, 308(19):4322--4331, 2008.

bibitem{ferrara} J.~Diemunsch, M.~Ferrara, S.~Jahanbekam, and J.~Shook. Extremal theorems for degree sequence packing and the 2-color discrete tomography problem. {em {S}{I}{A}{M} Journal of Discrete Mathematics}, 29(4):2088--2099, 2015.

bibitem{dirac} G.~Dirac. Some theorems on abstract graphs. {em Proceedings of the London Mathematical Society}, s3-2(1):69--81, 1952.

bibitem{gale} D.~Gale. A theorem on flows in networks. {em Pacific Journal of Mathematics}, 7(2):1073--1082, 1957.

bibitem{KSSz97} J.~Koml'os, G.~S'ark"ozy, and E.~Szemer'edi. Blow-up lemma. {em Combinatorica}, 17:109--123, 1997.

bibitem{KSSz98} J.~Koml'os, G.~S'ark"ozy, and E.~Szemer'edi. An algorithmic version of the blow-up lemma. {em Random Structures and Algorithms}, 12:297--312, 1998.

bibitem{KS93} J.~Koml'os and M.~Simonovits. Szemer'edi's regularity lemma and its applications in graph theory. {em Combinatorics: Paul ErdH{o}s is eighty}, 2:295--352, 1993.

bibitem{lovasz} L.~Lov'asz. {em {C}ombinatorial problems and exercises}. Corrected reprint of the 1993 second edition,

AMS Chelsea Publishing, Providence, RI, 2007.

bibitem{Ryan} R.~Martin. The edit distance in graphs: Methods, results, and generalizations. In A.~Beveridge, J.~Griggs, L.~Hogben, G.~Musiker, and P.~Tetali, editors, {em Recent Trends in Combinatorics}, pages 31--62. Springer International Publishing, Cham, 2016.

bibitem{ryser} H.~Ryser. Combinatorial properties of matrices of zeros and ones.

{em Canadian Journal of Mathematics}, 9:371--377, 1957.

bibitem{sissokho} M.~Sahs, P.~Sissokho, and J.~Torf. A zero-sum theorem over $mathbb{Z}$. {em Integers}, 13:#A70, 2013.

bibitem{SZ} E.~Szemer'edi. Regular partitions of graphs. {em Colloques Internationaux C.N.R.S textbf{260} - Probl`emes Combinatoires et Th'eorie des Graphes}, pages 399--401, 1976.

bibitem{west} D.~West. {em Introduction to graph theory}. Prentice Hall, Second edition, 2001.




DOI: https://doi.org/10.31449/inf.v43i1.2684

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.