Online Annual Meeting 3-5 May 2021
Title and abstracts of talks ordered alphabetically based on last name of the speakers.
Schedule at: https://www.irif.fr/~hosigra/pdfs/HOSIGRA-Program-2021.pdf
ZOOM link: https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09
Speaker: Mouhamad AL-JOUBBEH
Title: About Paths With three blocks.
Abstract: We show that every oriented path of order n > 4 with three blocks, in which two consecutive of them are of length 1, is contained in every (n + 1)-chromatic digraph.”
Speaker: Susobhan BANDOPADHYAY
Title. On (m,n)-absolute clique number of planar graphs.
Abstract. A mixed graph is a simple graph where a subset of the edges have been oriented to be arcs. An (m, n)-mixed graph is a graph where arcs have m different colors and edges have n different colors. The (m, n)- colored mixed graph and colored homomorphism was defined by Nešetril and Raspaud [J. Combin. Theory Ser. B 2000]. Colored homomorphism of an (m,n)-colored mixed graph G to an (m,n)-colored mixed graph H is a vertex mapping such that if uv is an arc (edge) of color c in G, then f(u)f(v) is also an arc (edge) of color c. The (m,n)-colored mixed chromatic number, χ_{m,n}(G) of G is the min{|V (H)|} such that G admits the colored homomorphism to H. An (m,n)-clique is an (m,n)-colored mixed graph G with χ_{m,n}(G) = |V (G)|. Later Bensmail, Duffy and Sen [Graphs Combin. 2017] extended the parameter absolute clique number to (m, n)-colored mixed graphs G, ω_{a(m,n)} (G). The (m, n)-absolute clique number of (m,n)-colored mixed graph G, ω_{a(m,n)}(G), the cardinality of largest absolute (m,n)-clique of G. Here we settle the conjecture on the absolute clique number for the family of planar graphs P, given by Bensmail, Duffy and Sen [Graphs Combin. 2017].
Speaker: Dibyayan CHAKRABORTY
Title: Finding Geometric Representations of Apex Graphs is NP-Hard.
Abstract: Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, \eg, circles (Koebe, 1936), line segments (Chalopin \& Gon{\c{c}}alves, 2009), \textsc{L}-shapes (Gon{\c{c}}alves~\etal, 2018). Furthermore, these representations can be obtained in polynomial time when the planar graph is provided as input. For general graphs, however, even deciding whether such representations exist is often $\NP$-hard. We consider apex graphs, \ie, graphs that can be made planar by removing one vertex from them. Somewhat surprisingly, we show that deciding whether geometric representations exist for apex graphs is also $\NP$-hard.
More precisely, we show that recognizing every graph class $\mathcal{G}$ which satisfies $\PureTwoDir\subseteq\mathcal{G}\subseteq\OneString$ is $\NP$-hard, even when the input graphs are apex graphs. Here, $\PureTwoDir$ is the class of intersection graphs of axis-parallel line segments (where intersections are allowed only between horizontal and vertical segments), and $\OneString$ is the class of intersection graphs of simple curves (where two curves share at most one point). Our proof is much simpler than previously known hardness reductions for these problems, and encapsulates several geometric graph classes in one.
Speaker: Dipayan CHAKRABORTY
Title: On clique numbers of colored mixed graphs
Abstract: An $(m,n)$-graph is a graph having $m$ different types of arcs and $n$ different types of edges. A homomorphism of an $(m,n)$-graph $G$ to another $H$ is a vertex mapping that preserves adjacency, its type and direction. A subset $R$ of vertices of $G$ that always maps to distinct vertices under any homomorphism is an $(m,n)$-relative clique of $G$. The maximum cardinality of an $(m,n)$-relative clique of a graph is called its $(m,n)$-relative clique number. In this article, we explore the $(m,n)$-relative clique number for different families of graphs.
Speaker: Arun Das
Title: Approximations for Orthogonal Line Centers
Abstract: $k$ orthogonal line center problem computes a set of $k$ axis-parallel lines for a given set of planer points such that the maximum among the distance between each point to its nearest line is minimized. A $2$-factor approximation algorithm and a $(\frac{7}{4}, \frac{3}{2})$ bi-criteria approximation algorithm is deviced for the problem. Both of them are deterministic approximation algorithms, having sub-quadratic running time.
This is a joint work with Professor Sandip Das and Dr. Joydeep Mukherjee.
Speaker: Soura Sena DAS
Title: On the relative oriented clique number of planar graphs
Abstract: A vertex subset $R$ of an oriented graph $\overrightarrow{G}$ is a relative oriented clique if each pair of non-adjacent vertices of $R$ is connected by a directed $2$-path. The relative oriented clique number $\omega_{ro}(\overrightarrow{G})$ of $\overrightarrow{G}$ is the maximum value of $|R|$ where $R$ is a relative oriented clique of $\overrightarrow{G}$. Given a family $\mathcal{F}$ of oriented graphs, the relative oriented clique number is $\omega_{ro}(\mathcal{F}) = \max\{\omega_{ro}(\overrightarrow{G})|\overrightarrow{G} \in \mathcal{F}\}$. For the family $\mathcal{P}_3$ of oriented planar graphs, and $\mathcal{P}_4$ of triangle-free oriented planar graphs, it was conjectured that $\omega_{ro}(\mathcal{P}_3)=15$ and $\omega_{ro}(\mathcal{P}_4)=10$. In this talk, we settle these conjectures.
Speaker: Sanjana Dey
Title: Discriminating codes in geometric setups
Abstract: We study two geometric variations of the discriminating code problem. In the \emph{discrete version}, a finite set of points $P$ and a finite set of objects $S$ are given in $\mathbb{R}^d$. The objective is to choose a subset $S^* \subseteq S$ of minimum cardinality such that the subsets $S_i^* \subseteq S^*$ covering $p_i$, satisfy $S_i^*\neq \emptyset$ for each $i=1,2,\ldots, n$, and $S_i^* \neq S_j^*$ for each pair $(i,j)$, $i \neq j$. In the \emph{continuous version}, the solution set $S^*$ can be chosen freely among a (potentially infinite) class of allowed geometric objects.
In the 1-dimensional case ($d=1$), the points are placed on some fixed-line $L$, and the objects in $S$ and $S^*$ are finite sub-segments of $L$ (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in 1D. We then design a polynomial-time $2$-approximation algorithm for the 1-dimensional discrete case. We also design a PTAS for both discrete and continuous cases when the intervals are all required to have the same length.
We then study the 2-dimensional case ($d=2$) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-hard, and design polynomial-time approximation algorithms with factors $4+\epsilon$ and $32+\epsilon$, respectively (for every fixed $\epsilon>0$).
Speaker: Harmender GAHLAWAT
Title: Applications of guarding techniques to Cops and Robber game
Abstract: Cops and Robber is a 2-player pursuit evasion game, where a set of cop (controlled by the first player) tries to capture the position of the robber (controlled by the second player). The main question regarding this game is about finding the minimum number of cops required to capture the robber in a graph, known as the cop number of the graph. Cops guard a subgraph, if the robber cannot enter that subgraph without getting captured. Guarding subgraphs of a graph have been used heavily to give bounds on the cop number of a graph. We will survey the use of guarding techniques for bounding the cop number of a graph and give results about the cop number of butterfly graphs and AT-free graphs.
Speaker: Fabien JACQUES
Title: The chromatic number of signed graphs with bounded maximum average degree.
Abstract: A signed graph is a simple graph with two types of edges: positive and negative. A homomorphism from a signed graph $G$ to another signed graph $H$ is a mapping $\varphi: V(G) \rightarrow V(H)$ that preserves adjacencies and balance of closed walk (the balance is the parity of the number of negative edges). The chromatic number $\chi_s(G)$ of a signed graph $G$ is the order of a smallest signed graph $H$ such that there is a homomorphism from $G$ to $H$. The maximum average degree $\mad(G)$ of a graph $G$ is the maximum of the average degrees of all the subgraphs of $G$. In this paper, we consider signed graphs with bounded maximum average degree and we prove that if $\mad(G) < \frac{8}{3}$ (resp. $\mad(G) < \frac{20}{7}$, $\mad(G) < \frac{10}{3}$, $\mad(G) < \frac{17}{5}$, $\mad(G) < 4-\frac{8}{q+3}$) then $\chi_s(G) \leq 4$ (resp. $\chi_s(G) \leq 5$, $\chi_s(G) \leq 9$, $\chi_s(G) \leq 10$, $\chi_s(G) \leq q+1$ with $q$ a prime power congruent to 1 modulo 4).
Joint work with Alexandre Pinlou.
Speaker: Yiting JIANG
Title: Twin-width and generalized coloring numbers
Abstract: In this paper, we prove that a graph $G$ with no $K_{s,s}$-subgraph and twin-width $d$ has $r$-admissibility and $r$-coloring numbers bounded by an exponential function of $r$, and that we can construct graphs achieving such a dependency in $r$.
Joint work with Jan Dreier, Jakub Gajarsky, Patrice Ossona de Mendez and Jean-Florent Raymond.
Speaker: Arnott KIDNER
Title: The Switch Homomorphism Problem is Polynomial When the Target is K_2
Abstract: An $(m,n)$-mixed graph is a mixed graph whose edge sets are partitioned into $n$ colours, and whose arc sets are partitioned into $m$ colours
Let $G$ be a (m,n)-mixed graph, $\Gamma$ be a permutation group acting on the colours of $G$, and $\pi \in \Gamma$ be a permutation. We define \emph{switching a vertex $v$ with respect to $\pi$} as acting on the colour of each edge incident to $v$ with $\pi$.
Two graphs $G$ and $H$ are \emph{switch equivalent} with respect to $\Gamma$ if there is a sequence of switches $\Sigma= ((v_0,\pi_0), (v_1,\pi_1), \cdots, (v_k,\pi_k) )$ such that after $\Sigma$, $G = H$.
Question:Does $G$ admit a switch homomorphism to $H$ under the group action of $\Gamma$?
We show that this problem is polynomial for all $\Gamma$.
Speaker: Dimitri LAJOU
Title: Vertex deletion and edge deletion problems for homomorphism of signed graphs
Abstract: The problem VERTEX DELETION SIGNED-(H,pi)-COLORING takes as input a signed graph (G,sigma) and a positive integer k. An instance of this problem is positive if there exists a set S of at most k vertices of G such that (G,sigma) - S admits a homomorphism to (H,pi). The problem EDGE DELETION SIGNED-(H,pi)-COLORING is defined in a similar way. This talk is a follow up to the work done at the last HOSIGRA meeting in Sete (2019) which produced the paper [1].
We completely caracterize the parameterized complexity of the problems VERTEX DELETION SIGNED-(H,pi)-COLORING and EDGE DELETION SIGNED-(H,pi)-COLORING parameterized by the solution size for any signed graph (H,pi). We determine which problem are NP-complete and which are polynomial. For the NP-complete problems which are in XP, we also provide FPT algorithms solving them.
Reference: [1] Parameterized complexity of edge-coloured and signed graph homomorphism problems Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron
Speaker: Suchismita MISHRA
Title: Cliques in exact distance powers of graphs
Abstract: The exact p-power of a graph G, denoted G^{\#p}, is a graph on vertex set V (G) and two vertices are adjacent if they are at distance p in G. Let G be a graph with maximum degree k + 1. We can easily observed that the largest possible clique in G^{\#2} is of size at most k^2+k+1. We prove that G^{\#p} has a clique of size k^2+k+1 if and only if a connected component of G is isomorphic to the incidence graph of a projective k-geometry (these famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k). We then study the case of graphs of maximum degree k + 1 whose exact p-power has clique number k^2 + k. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k^2 + k)-clique, either G has a subgraph isomorphic to the incidence graph of a projective k-geometry minus a vertex or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k^2 + k). We study the structural properties of all such graphs. We show these graphs are highly symmetric. Also we show that if G is a 3-regular bipartite graph such that ω(G^{\#2})=6, then it is isomorphic to the Franklin graph. We then show that up to isomorphism there is only one 4-regular bipartite graph whose exact square has clique number 12. In fact we construct that graph. Furthermore, we show for k = 4, 5 there is no k-regular bipartite graph whose exact square has clique number k^2 + k.
Given integers k and p, we define f(k, p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. For general values of p, we prove that f(k, p) ≤ (k + 1)k \ceil{p/2} + 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k.
Speaker: Jonathan Narboni
Title: Coloring signed graphs with given cyclomatic number
Abstract: The cyclomatic number of a graph $G$ is defined as the size of a cycle basis of $G$, equivalently, it is the number of edges to delete in $G$ in order to obtain a forest. In this talk, we give upper and lower bounds on both the chromatic number and the choice number of signed graphs a given cyclomatic number. We also show that deciding if a signed graph has a chromatic number at most $k$ is FPT when parametrized by the cyclomatic number.
This is joint work with Jan Bok, Nikola Jedli\v{c}kov\'{a}, Dimitri Lajou, and \'{E}ric Sopena
Speaker: Nacim OIJID
Title: Achromatic number of signed graphs.
Abstract: Graph coloring is one of the most famous problems in Graph Theory. It has been declined into many problems by adding constraints. One of them is the notion of achromatic number, which is defined as the largest number of colors we can use to color a graph in such a way that each pair of colors appears on at least one edge. This notion of achromatic number has already led to many results on undirected graphs.
During this talk, I will present results on the achromatic number of signed graphs, obtained in collaboration with Julien Bensmail, François Dross and Eric Sopena during a three-month internship. We will see how classical operations on a signed graph can modify the achromatic number and what the complexity of computing this parameter is.
Speaker: Pavan P D
Title: On Deeply Critical Oriented Cliques
Abstract: In this work we consider arc criticality in colourings of oriented graphs. We study deeply critical oriented graphs, those graphs for which the removal of any arc results in a decrease of the oriented chromatic number by $2$. We prove the existence of deeply critical oriented cliques of every odd order $n\geq 9$, closing an open question posed by Borodin et al. (Journal of Combinatorial Theory, Series B, 81(1):150–155, 2001). Additionally, we prove the non-existence of deeply critical oriented cliques among the family of circulant oriented cliques of even order.
Speaker: Lan Anh PHAM
Title: Complex and homomorphic chromatic number of signed planar simple graphs
Abstract: Given the set C_{k,l}={±1,±2,...,±k} ∪ {±1i,±2i,...,±ki}, where i=\sqrt{-1}, a signed graph (G, σ) is said to be (k,l)-colorable if there exists a mapping c of the vertices of G to C_{k+l} such that for every edge xy of G we have c(x)c(y) ≠ σ(xy) |c(x)^2|. The complex chromatic number of a signed graph (G, σ) is defined to be the smallest order of C_{k,l} such that (G, σ) admits a (k,l)-coloring.
In this talk, we show that there are signed planar simple graphs which are not 4-colorable. That is to say: there is a signed planar simple graph which is neither (2,0)-colorable, nor (1,1)-colorable, nor (0,2)-colorable. That every signed planar simple graph is (2,0)-colorable was the subject of a conjecture by Máčajová, Raspaud and Skoviera which was recently disproved by Kardoš and Narboni using a dual notion. We provide a direct approach and a short proof. That every signed planar simple graph is (1,1)-colorable is a recent conjecture of Jiang and Zhu.
Furthermore, from a homomorphism point of view, we find three minimal graphs on three vertices each of which bounds the class of signed planar simple graphs.
Joint work with Reza Naserasr.
Paper is available on: https://hal.archives-ouvertes.fr/hal-03000542/document
Speaker: Taruni S
Title : On chromatic number of (n, m)-graphs
Abstract : A (n, m)-colored mixed graph is a graph with n types of arcs and m types of edges. The chromatic number is defined as the minimum number of colors to color the vertices of the graph such that if we identify the vertices of the same color, what we get is a simple (n, m)- colored mixed graph by identifying the arcs/edges between two vertices which have the same direction and/or color. We study the said chromatic number for the family of sparse graphs, graphs with bounded maximum degree and degeneracy. We also probe the parameter for partial 2-trees when 2n + m = 3.
Speaker: Ritesh SETH
Title: The Relative Signed Clique Number of Planar Graphs is 8
Abstract: A simple signed graph $(G,\Sigma)$ is a simple graph with a $+$ve or a $-$ve sign assigned to each of its edges where $\Sigma$ denotes the set of $-$ve edges. A cycle is unbalanced if it has an odd number of $-$ve edges. A vertex subset $R$ of $(G,\Sigma)$ is a relative signed clique if each pair of non-adjacent vertices of $R$ is part of an unbalanced $4-$cycle. The relative signed clique number $\omega_{rs}((G,\Sigma))$ of $(G,\Sigma)$ is the maximum value of $|R|$ where $R$ is a relative signed clique of $(G,\Sigma)$. Given a family $\mathcal{F}$ of signed graphs, the relative signed clique number is $\omega_{rs}(\mathcal{F})=max\{\omega_{rs}((G,\Sigma))|(G,\Sigma)\in \mathcal{F}\}$. For the family $\mathcal{P}_3$ of signed planar graphs, the problem of finding the value of $\omega_{rs}(\mathcal{P}_3)$ is an open problem. In this article, we close it by proving $\omega(\mathcal{P}_3) = 8$.
Speaker: Zhouningxin WANG
Title: Mapping signed sparse graphs to $(K_{2k}, M)$.
Abstract: A signed graph $(G, \sigma)$ is a graph $G$ (loops and multi-edges allowed) together with an assignment $\sigma: E(G) \to \{+, -\}$. A homomorphism of a signed graph $(G, \sigma)$ to $(H, \pi)$ is a mapping of vertices and edges of $G$ respectively to the vertices and edges of $H$ such that the adjacencies, the incidences, and the signs of closed walks are preserved. Motivated by reformulations of the $k$-coloring problem in this language, and especially in connection with results on $3$-coloring of planar graphs, such as Gr\"{o}tzsch's theorem, we consider bounds on the maximum average degree which are sufficient for mapping signed graphs to the signed graph $(K_{2k}, M)$ ($k\geq 3$) where the negative edges form a perfect matching. In this talk, we show that for $k=3$ the maximum average degree strictly less than $\frac{14}{5}$ is sufficient and for values of $k\geq 4$, we find the best maximum average degree bound to be $3$. Moreover, we discuss the applications of our work to signed planar graphs and propose questions similar to Steinberg's conjecture for the class of signed bipartite planar graphs.
Joint work with Reza Naserasr, Riste Skrekovski, Rongxing Xu.
Speaker: Weiqiang YU
Title: Separating two signatures in signed planar graphs
Abstract: A signed graph $(G, \sigma)$ is a graph together with a signature which is an assignment of signs to the edges. A switching at a vertex $v$ is to reverse the sign of each edge incident to $v$. Two signatures $\sigma_1$ and $\sigma_2$ on $G$ are equivalent if one can be obtained from the other by a sequence of switchings. The \emph{signature packing number} of a signed graph $(G, \sigma)$, denoted $\rho(G, \sigma)$, is defined to be the maximum number of signatures $\sigma_1, \sigma_2,\cdots, \sigma_l$ such that each $\sigma_i$ is switching equivalent to $\sigma$ and the sets of negative edges of $(G, \sigma_1)$'s are pairwise disjoint.
As a generalization of packing number, instead of considering one signature and its equivalent signatures, we consider $k$ signatures $\sigma_1, \sigma_2,\cdots, \sigma_k$ (not necessarily switching equivalent) and ask whether there exist signatures $\sigma_{1}', \sigma_{2}',\cdots, \sigma_{k}'$, where $\sigma_{i}'$ is a switching of $\sigma_{i}$, such that the sets of negative edges $E^{-}_{\sigma_{i}'}$ are pairwise disjoint.
It is known that there exists signed planar graph whose packing number is $1$. Thus for a general planar graph separating two signatures is not always possible even if $\sigma_{1}=\sigma_{2}$. In this work, we prove that given planar graph $G$ which satisfies one of the following conditions: no pair of triangles sharing a vertex, no $4$-cycle, no $5$-cycle, no $6$-cycle, and any two signatures $\sigma$ and $\pi$ on $G$, there are switchings $\sigma'$ and $\pi'$ of $\sigma$ and $\pi$, respectively, such that $E_{\sigma'}^}\cap E_{\pi'}^{=\varnothing$.
Joint work with Reza Naserasr.
Speaker: Rongxing XU
Title: The strong fractional choice number of graphs.
Abstract: Assume $G$ is a graph and $r$ is a real number. We say $G$ is \emph{ strongly fractional $r$-choosable} if $G$ is $(a,b)$-choosable for any $(a,b)$ for which $\frac ab \ge r$. The {\em strong fractional choice number} of $G$ is defined as $ch^s_f(G)= \inf \{r \in \mathbf{R}: \text{$G$ is strongly fractional $r$-choosable}\}$. The strong fractional choice number of a family $\mathcal{G}$ of graphs is the supremum of the strong fractional choice number of graphs in $\mathcal{G}$. In this talk, I will introduce some basic properties of the strong fractional choice number of graphs, and the value or lower bound and upper bound of these parameters for some special classes of graphs. For example, we show that every bipartite $3$-choice-critical graph has strong fractional number $2$; the strong fractional choice number of the family of planar graphs without $4$-cycle and $5$-cycle is at least $4+1/12$; the strong fractional choice number of the family of planar graphs is at least $4+1/3$. The last result improves a lower bound $4+2/9$ in [X. Zhu. Multiple list colouring of planar graphs. J. Combin. Theory Ser. B, 122:794– 799, 2017].
Joint work with Xuding Zhu.
Speaker: Huan ZHOU
Title: Circular coloring of signed graphs of bounded treewidth
Abstract: Circular r-coloring of a signed graph (G, \sigma) is a mapping f of vertices of G to the point of a circle of circumference r such that: if $xy$ is a positive edge of (G, \sigma) then $f(x)$ and $f(y)$ are at distance at least 1 and if $xy$ is a negative edge of (G, \sigma) then $f(x)$ and the antipodal of $f(y)$ are at distance at least 1. The smallest $r$ for which $(G,\sigma)$ admits a circular r-coloring is the circular chromatic number of $(G, \sigma)$.
In this work we study circular chromatic number of signed graphs where $G$ is of treewidth at most $k$. We show that for every $\epsilon > 0$ and $k$, there exists an integer $g$ such that if the negative-girth of $(G, -\sigma)$ is at least $g$ and $G$ is of treewidth at most $k$, then the circular chromatic number of $(G, \sigma)$ is at most $2+\epsilon$.