Let $G$ be a graph of minimum degree at least $v(G)/2$. Can we color the edges of~$G$ with red and blue so that every non-adjacent pair of vertices is connected by a path consisting of $exactly$ one red edge and one blue edge? In this talk, we provide an affirmative answer when $G$ is ``close'' to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. We also discuss an asymptotic version of this question.
This is joint work with János Barát and Andrea Freschi.
Egy gráf részleges élszínezésének kiterjesztése alatt azt értjük, hogy a gráf éleinek egy részhalmazát jól színezve mikor egészíthető ki ez az előszínezés a teljes gráf jó élszínezésévé úgy, hogy nem használunk a megengedettnél (jellemzően a kromatikus indexnél) több színt. Röviden áttekintjük a probléma hátterét és néhány klasszikus eredményt, majd Descartes-szorzatokra, illetve speciális esetként hiperkockákra vonatkozó kiterjesztési tételeket tárgyalunk.
Az előadás középpontjában olyan eredmények állnak, amelyekben az előszínezett élek egymástól való távolságára teszünk feltételeket. Páros gráfok Descartes-szorzatában egy természetes fokszámfeltétel mellett a 3-távolságú párosítások, hiperkockákban pedig 2-távolságú párosítások előszínezésének kiterjeszthetőségét igazoljuk.
Az eredmények Győri Ervinnel közösek.
A directed graph is called acyclic if it contains no directed circuit, and totally cyclic if every arc belongs to a directed circuit. For a graph $G$, let $\tau(G)$, $a(G)$, and $c(G)$ denote, respectively, the numbers of spanning trees, acyclic orientations, and totally cyclic orientations of $G$. The Merino–Welsh conjecture states that $\tau(G)\leq \max{a(G),c(G)}$ for every bridgeless and loopless multigraph $G$.
In this talk, we will briefly discuss the history of the conjecture and its connection with the Tutte polynomial. We will then present improved bounds on the edge density that guarantee the conjecture in the sparse and dense regimes.
Egy $n$-változós Boole-függvény érzékenysége egy adott $x$ inputon azon bitjeinek száma, amit megváltoztatva a függvény értéke is megváltozik. A függvény érzékenysége a legnagyobb érzékenység a $2^n$ input között. A blokk-érzékenység ennek egy általánosítása: bitek helyett bit-blokkok megfordításával kell az értéket megváltoztatni és a páronként diszjunkt blokkok számát maximalizáljuk. Technikailag nagyon hasznos fogalom legalább akkora mint az érzékenység. Sokan azt gondolták, hogy sokkal nagyobb nem is lehet.
Szegedy és Nisan 1994-ben sejtette, hogy az érzékenység és blokk-érzékenység közötti kapcsolat polinomiális. Több mint 25 évig a sejtés egy központi megoldatlan probléma volt. 2019-ben Huang megoldotta a sejtést egyszerű érveléssel, ami BSc-s lineáris algebrai ismeretekre támaszkodott.
Az előadás a kérdés hátteréről, példákról és a megoldásról szól.
Egy izolált csúcsoktól mentes $G$ gráfban az $S\subseteq V$ ponthalmaz totálisan domináló, ha minden $V$-beli csúcsnak van $S$-beli szomszédja. Azt mondjuk két csúcsrészhalmazra $X,Y\subseteq V$, hogy ők totális koalíciót alkotnak, ha egyikük sem totálisan domináló halmaz, de $X\cup Y$ már az.
A $G$ gráf $\Psi=\{V_1,V_2,\dots,V_k\}$ csúcspartíciója egy totális koalíció partíció, ha tetszőleges $V_i$-hez létezik olyan $V_j$, amivel együtt ők totális koalíciót alkotnak. Jelölje $C_t(G)$ azt a legnagyobb $k$ egész számot, amire létezik $k$ osztályú totális koalíció partíció. Ezt nevezzük a $G$ gráf totális koalíció számának.
Barát és Blázsik éles alsó és felső korlátot bizonyítottak a totális koalíció számra a gráf maximális és minimális fokszámának segítségével, amiből 3-reguláris gráfokra az következik, hogy $4\le C_t(G)\le 6$. A mostani előadásban arra fókuszálnék, amit ezek után Michael A. Henninggel és közösen témavezetett doktoranduszunkkal (Shahin N. Jogan) együtt csináltunk karommentes, $3$-reguláris gráfok totális koalíció számával kapcsolatban.