Rose McCarty, Circle graphs are polynomially chi-bounded

Room B232 IBS (기초과학연구원)

Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords, and two vertices are adjacent if their chords intersect. We prove that every circle graph with clique number k has chromatic number at most $4k^2$. Joint with James Davies.

Sang June Lee (이상준), On strong Sidon sets of integers

Room B232 IBS (기초과학연구원)

Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$, with $a_1,a_2\in S$ and $a_1\leq a_2$, are distinct, or equivalently, if \ for every $x,y,z,w\in S$ with $x<y\leq z<w$. We define strong Sidon sets as follows: For a constant $\alpha$ with $0\leq

Xin Zhang (张欣), On equitable tree-colorings of graphs

Room B232 IBS (기초과학연구원)

An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably

Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs

Room B232 IBS (기초과학연구원)

A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors. The $b$-chromatic number of a graph $G$, denoted

Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

Room B232 IBS (기초과학연구원)

Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent

Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues

Room B232 IBS (기초과학연구원)

An odd $$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$, $1 \le d_H(v) \le b$, and $d_H(v)$ is odd. For positive integers $r \ge 3$ and $b \le r$, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of

Patrice Ossona de Mendez, A model theoretical approach to sparsity

Room B232 IBS (기초과학연구원)

We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

Dabeen Lee (이다빈), Integrality of set covering polyhedra and clutter minors

Room B232 IBS (기초과학연구원)

Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem, also known as the hitting set problem, admits a simple integer linear programming formulation. The constraint

2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

Room B232 IBS (기초과학연구원)

Schedule July 22 Monday 10:00-11:00 Introduction, 11:00-12:00 Open Problems July 23 Tuesday 10:00-10:30 Stefan Kratsch, Humboldt-Universität zu Berlin, Germany Elimination Distances, Blocking Sets, and Kernels for Vertex Cover 10:45-11:15 Benjamin Bergougnoux, University Clermont Auvergne, France More applications of the d-neighbor equivalence 11:30-12:00 Yixin Cao, Hong Kong Polytechnic University, China Enumerating Maximal Induced Subgraphs 13:30-14:30 Open Problems

2019-2 IBS One-Day Conference on Extremal Graph Theory

Room B232 IBS (기초과학연구원)

Invited Speakers Jaehoon Kim (김재훈), KAIST Hong Liu (刘鸿), University of Warwick Abhishek Methuku, IBS Discrete Mathematics Group Péter Pál Pach, Budapest University of Technology and Economics Schedule August 12, Monday 11:00am-12:00pm Jaehoon Kim (김재훈): Tree decompositions of graphs without large bipartite holes 12:00pm-1:30pm Lunch 1:30pm-2:30pm Abhishek Methuku: Bipartite Turán problems for ordered graphs 3:00pm-4:00pm Péter Pál

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.