Source author record

Teeradej Kittipassorn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A strategy for Isolator in the Toucher-Isolator game on trees

In the Toucher-Isolator game, introduced recently by Dowden, Kang, Mikalački and Stojaković, Toucher and Isolator alternately claim an edge from a graph such that Toucher aims to touch as many vertices as possible, while Isolator aims to isolate as many vertices as possible, where Toucher plays first. Among trees with $n$ vertices, they showed that the star is the best choice for Isolator and they asked for the most suitable tree for Toucher. Later, Räty showed that the answer is the path with $n$ vertices. We give a simple alternative proof of this result. The method to determine where Isolator should play is by breaking down the gains and losses in each move of both players.

preprint2020arXiv

The graph grabbing game on blow-ups of trees and cycles

The graph grabbing game is played on a non-negatively weighted connected graph by Alice and Bob who alternately claim a non-cut vertex from the remaining graph, where Alice plays first, to maximize the weights on their respective claimed vertices at the end of the game when all vertices have been claimed. Seacrest and Seacrest conjectured that Alice can secure at least half of the weight of every weighted connected bipartite even graph. Later, Egawa, Enomoto and Matsumoto partially confirmed this conjecture by showing that Alice wins the game on a class of weighted connected bipartite even graphs called $K_{m,n}$ -trees. We extend the result on this class to include a number of graphs, e.g. even blow-ups of trees and cycles.

preprint2016arXiv

A canonical Ramsey theorem for exactly $m$ -coloured complete subgraphs

Given an edge colouring of a graph with a set of $m$ colours, we say that the graph is (exactly) $m$ -coloured if each of the colours is used. We consider edge colourings of the complete graph on $\mathbb{N}$ with infinitely many colours and show that either one can find an $m$ -coloured complete subgraph for every natural number $m$ or there exists an infinite subset $X \subset \mathbb{N}$ coloured in one of two canonical ways: either the colouring is injective on $X$ or there exists a distinguished vertex $v$ in $X$ such that $X \setminus \lbrace v \rbrace$ is $1$ -coloured and each edge between $v$ and $X \setminus \lbrace v \rbrace$ has a distinct colour (all different to the colour used on $X \setminus \lbrace v \rbrace$ ). This answers a question posed by Stacey and Weidl in 1999. The techniques that we develop also enable us to resolve some further questions about finding $m$ -coloured complete subgraphs in colourings with finitely many colours.

preprint2016arXiv

Approximations to $m$ -coloured complete infinite hypergraphs

Given an edge colouring of a graph with a set of $m$ colours, we say that the graph is (exactly) $m$ -coloured if each of the colours is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number $m>2$ and for all sufficiently large $k$ , there is a $k$ -colouring of the complete graph on $\mathbb{N}$ such that no complete infinite subgraph is exactly $m$ -coloured. In the light of this result, we consider the question of how close we can come to finding an exactly $m$ -coloured complete infinite subgraph. We show that for a natural number $m$ and any finite colouring of the edges of the complete graph on $\mathbb{N}$ with $m$ or more colours, there is an exactly ${\hat m}$ -coloured complete infinite subgraph for some ${\hat m}$ satisfying $|m-{\hat m}|\le \sqrt{m/2} + 1/2$ ; this is best-possible up to the additive constant. We also obtain analogous results for this problem in the setting of $r$ -uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalisations of this conjecture to $r$ -uniform hypergraphs.

preprint2016arXiv

Disjoint induced subgraphs of the same order and size

For a graph $G$ , let $f(G)$ be the largest integer $k$ for which there exist two vertex-disjoint induced subgraphs of $G$ each on $k$ vertices, both inducing the same number of edges. We prove that $f(G) \ge n/2 - o(n)$ for every graph $G$ on $n$ vertices. This answers a question of Caro and Yuster.

preprint2016arXiv

Separating path systems

We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$ -vertex graph admits a separating path system of size $O(n)$ and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.

preprint2015arXiv

Frustrated Triangles

A triple of vertices in a graph is a \emph{frustrated triangle} if it induces an odd number of edges. We study the set $F_n\subset[0,\binom{n}{3}]$ of possible number of frustrated triangles $f(G)$ in a graph $G$ on $n$ vertices. We prove that about two thirds of the numbers in $[0,n^{3/2}]$ cannot appear in $F_n$ , and we characterise the graphs $G$ with $f(G)\in[0,n^{3/2}]$ . More precisely, our main result is that, for each $n\geq 3$ , $F_n$ contains two interlacing sequences $0=a_0\leq b_0\leq a_1\leq b_1\leq \dots \leq a_m\leq b_m\sim n^{3/2}$ such that $F_n\cap(b_t,a_{t+1})=\emptyset$ for all $t$ , where the gaps are $|b_t-a_{t+1}|=(n-2)-t(t+1)$ and $|a_t-b_t|=t(t-1)$ . Moreover, $f(G)\in[a_t,b_t]$ if and only if $G$ can be obtained from a complete bipartite graph by flipping exactly $t$ edges/nonedges. On the other hand, we show, for all $n$ sufficiently large, that if $m\in[f(n),\binom{n}{3}-f(n)]$ , then $m\in F_n$ where $f(n)$ is asymptotically best possible with $f(n)\sim n^{3/2}$ for $n$ even and $f(n)\sim \sqrt{2}n^{3/2}$ for $n$ odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with $n$ vertices and $e\leq n^2/4$ edges.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Teeradej Kittipassorn

Research overview

Is this your work?

7 publications

A strategy for Isolator in the Toucher-Isolator game on trees

The graph grabbing game on blow-ups of trees and cycles

A canonical Ramsey theorem for exactly $m$ -coloured complete subgraphs

Approximations to $m$ -coloured complete infinite hypergraphs

Disjoint induced subgraphs of the same order and size

Separating path systems

Frustrated Triangles

See the researcher in context

Building this map preview

Teeradej Kittipassorn

Research overview

Is this your work?

7 publications

A strategy for Isolator in the Toucher-Isolator game on trees

The graph grabbing game on blow-ups of trees and cycles

A canonical Ramsey theorem for exactly mmm-coloured complete subgraphs

Approximations to mmm-coloured complete infinite hypergraphs

Disjoint induced subgraphs of the same order and size

Separating path systems

Frustrated Triangles

See the researcher in context

Building this map preview

A canonical Ramsey theorem for exactly $m$ -coloured complete subgraphs

Approximations to $m$ -coloured complete infinite hypergraphs