Source author record

Michał Dębski

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws

For graphs $G$ and $H$ , an $H$ -coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$ . In the $H$ -Coloring problem the graph $H$ is fixed and we ask whether an instance graph $G$ admits an $H$ -coloring. A generalization of this problem is $H$ -ColoringExt, where some vertices of $G$ are already mapped to vertices of $H$ and we ask if this partial mapping can be extended to an $H$ -coloring. We study the complexity of variants of $H$ -Coloring in $F$ -free graphs, i.e., graphs excluding a fixed graph $F$ as an induced subgraph. For integers $a,b,c \geq 1$ , by $S_{a,b,c}$ we denote the graph obtained by identifying one endvertex of three paths on $a+1$ , $b+1$ , and $c+1$ vertices, respectively. For odd $k \geq 5$ , by $W_k$ we denote the graph obtained from the $k$ -cycle by adding a universal vertex. As our main algorithmic result we show that $W_5$ -ColoringExt is polynomial-time solvable in $S_{2,1,1}$ -free graphs. This result exhibits an interesting non-monotonicity of $H$ -ColoringExt with respect to taking induced subgraphs of $H$ . Indeed, $W_5$ contains a triangle, and $K_3$ -Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., $S_{1,1,1}$ -free) graphs. Our algorithm is based on two main observations: 1. $W_5$ -ColoringExt in $S_{2,1,1}$ -free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2. the latter problem can be solved in polynomial time in $S_{2,1,1}$ -free graphs. We complement this algorithmic result with several negative ones. In particular, we show that $W_5$ -ColoringExt is NP-hard in $S_{3,3,3}$ -free graphs. This is again uncommon, as usually problems that are NP-hard in $S_{a,b,c}$ -free graphs for some constant $a,b,c$ are already hard in claw-free graphs.

preprint2020arXiv

Conflict-free chromatic number vs conflict-free chromatic index

A vertex coloring of a given graph $G$ is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e. a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of $G$ , denoted $χ_{CF}(G)$ . What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree $Δ$ ? Trivially, $χ_{CF}(G)\leq χ(G)\leq Δ+1$ , but it is far from optimal - due to results of Glebov, Szabó and Tardos, and of Bhyravarapu, Kalyanasundaram and Mathew, the answer in known to be $Θ\left(\ln^2Δ\right)$ . We show that the answer to the same question in the class of line graphs is $Θ\left(\lnΔ\right)$ - that is, the extremal value of the conflict-free chromatic index among graphs with maximum degree $Δ$ is much smaller than the one for conflict-free chromatic number. The same result for $χ_{CF}(G)$ is also provided in the class of near regular graphs, i.e. graphs with minimum degree $δ\geq αΔ$ .

preprint2013arXiv

Strong chromatic index of sparse graphs

A coloring of the edges of a graph $G$ is strong if each color class is an induced matching of $G$ . The strong chromatic index of $G$ , denoted by $χ_{s}^{\prime}(G)$ , is the least number of colors in a strong edge coloring of $G$ . In this note we prove that $χ_{s}^{\prime}(G)\leq (4k-1)Δ(G)-k(2k+1)+1$ for every $k$ -degenerate graph $G$ . This confirms the strong version of conjecture stated recently by Chang and Narayanan [3]. Our approach allows also to improve the upper bound from [3] for chordless graphs. We get that $% χ_{s}^{\prime}(G)\leq 4Δ-3$ for any chordless graph $G$ . Both bounds remain valid for the list version of the strong edge coloring of these graphs.

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.