Gap vertex-distinguishing edge colorings of graphs

In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph $G$ which induces a vertex distinguishing labeling of $G$ such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of $G$ is called the gap chromatic number of $G$ and is denoted by $\mathrm{gap}\left(G\right)$.We here study the gap chromatic number for a large set of graphs $G$ of order $n$ and prove that $\mathrm{gap}\left(G\right)\in \{n?1,n,n+1\}$.     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

Independent Domination in Triangle Graphs

We study the complexity of INDEPENDENT DOMINATION, a well-known algorithmical problem, for triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in $G-I$, there is a vertex $w\in I$ such that $\{u,v,w\}$ induces a triangle in G. We show that INDEPENDENT DOMINATION within triangle graphs is closely connected with the general STABLE MAX-CUT problem. However, the INDEPENDENT DOMINATION problem is NP-complete for K_1,4-free triangle graphs. Finally, we investigate some natural invariants related to independent domination from the algorithmical point of view and apply our results to triangle graphs.     

On Vertex Partitions and the Colin de Verdière Parameter

We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with $\mu (G)⩾2$ admits a vertex partition into two graphs with μ at most $\mu (G)-1$. Here we prove that any graph G with $\mu (G)⩾3$ admits a vertex partition into three graphs with μ at most $\mu (G)-2$. This study is extended to other minor-monotone graph parameters like the Hadwiger number.     

On 1-uniqueness and dense critical graphs for tree-depth

The tree-depth of $G$ is the smallest value of $k$ for which a labeling of the vertices of $G$ with elements from $\{1,\dots ,k\}$ exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is $k$-critical if it has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth.Motivated by a conjecture on the maximum degree of $k$-critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that $(n?1)$-critical graphs on $n$ vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth.