Source author record

Carl Feghali

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

16works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Solution to a problem of Katona on counting cliques of weighted graphs

A subset $I$ of the vertex set $V(G)$ of a graph $G$ is called a $k$ -clique independent set of $G$ if no $k$ vertices in $I$ form a $k$ -clique of $G$ . An independent set is a $2$ -clique independent set. Let $π_k(G)$ denote the number of $k$ -cliques of $G$ . For a function $w: V(G) \rightarrow \{0, 1, 2, \dots\}$ , let $G(w)$ be the graph obtained from $G$ by replacing each vertex $v$ by a $w(v)$ -clique $K^v$ and making each vertex of $K^u$ adjacent to each vertex of $K^v$ for each edge $\{u,v\}$ of $G$ . For an integer $m \geq 1$ , consider any $w$ with $\sum_{v \in V(G)} w(v) = m$ . For $U \subseteq V(G)$ , we say that $w$ is uniform on $U$ if $w(v) = 0$ for each $v \in V(G) \setminus U$ and, for each $u \in U$ , $w(u) = \left\lfloor m/|U| \right\rfloor$ or $w(u) = \left\lceil m/|U| \right\rceil$ . Katona asked if $π_k(G(w))$ is smallest when $w$ is uniform on a largest $k$ -clique independent set of $G$ . He placed particular emphasis on the Sperner graph $B_n$ , given by $V(B_n) = \{X \colon X \subseteq \{1, \dots, n\}\}$ and $E(B_n) = \{\{X,Y\} \colon X \subsetneq Y \in V(B_n)\}$ . He provided an affirmative answer for $k = 2$ (and any $G$ ). We determine graphs for which the answer is negative for every $k \geq 3$ . These include $B_n$ for $n \geq 2$ . Generalizing Sperner's Theorem and a recent result of Qian, Engel and Xu, we show that $π_k(B_n(w))$ is smallest when $w$ is uniform on a largest independent set of $B_n$ . We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs.

preprint2022arXiv

1-Extendability of independent sets

In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in $2^{o(n)}$ time assuming the Exponential Time Hypothesis, where $n$ is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a. Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability.

preprint2022arXiv

A note on Matching-Cut in $P_t$ -free Graphs

A matching-cut of a graph is an edge cut that is a matching. The problem Matching-Cut is that of recognizing graphs with a matching-cut and is NP-complete, even if the graph belongs to one of a number of classes. We initiate the study of Matching-Cut for graphs without a fixed path as an induced subgraph. We show that Matching-Cut is in P for $P_5$ -free graphs, but that there exists an integer $t > 0$ for which it is NP-complete for $P_{t}$ -free graphs.

preprint2022arXiv

Kempe equivalence of $4$ -critical planar graphs

Answering a question of Mohar from 2007, we show that for every $4$ -critical planar graph, its set of $4$ -colorings is a Kempe class.

preprint2022arXiv

Strengthening a theorem of Meyniel

For an integer $k \geq 1$ and a graph $G$ , let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whenever the coloring~ $β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$ . We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$ .

preprint2021arXiv

The maximum sum of sizes of cross-intersecting families of subsets of a set

A set of sets is called a family. Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each member of $\mathcal{A}$ intersects each member of $\mathcal{B}$ . For any two integers $n$ and $k$ with $1 \leq k \leq n$ , let ${[n] \choose \leq k}$ denote the family of subsets of $[n] = \{1, \dots, n\}$ that have at most $k$ elements. We show that if $\mathcal{A}$ is a non-empty subfamily of ${[n] \choose \leq r}$ , $\mathcal{B}$ is a non-empty subfamily of ${[n] \choose \leq s}$ , $r \leq s$ , and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $|\mathcal{A}| + |\mathcal{B}| \leq 1 + \sum_{i=1}^s \left({n \choose i} - {n-r \choose i} \right),$ and equality holds if $\mathcal{A} = \{[r]\}$ and $\mathcal{B}$ is the family of sets in ${[n] \choose \leq s}$ that intersect $[r]$ .

preprint2020arXiv

A Thomassen-type method for planar graph recoloring

The reconfiguration graph $R_k(G)$ for the $k$ -colorings of a graph $G$ has as vertices all possible $k$ -colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. We use a list coloring technique inspired by results of Thomassen to prove that for a planar graph $G$ with $n$ vertices, $R_{10}(G)$ has diameter at most $8n$ , and if $G$ is triangle-free, then $R_7(G)$ has diameter at most $7n$ .

preprint2020arXiv

An Erdős-Ko-Rado Theorem for unions of length 2 paths

A family of sets is intersecting if any two sets in the family intersect. Given a graph $G$ and an integer $r\geq 1$ , let $\mathcal{I}^{(r)}(G)$ denote the family of independent sets of size $r$ of $G$ . For a vertex $v$ of $G$ , the family of independent sets of size $r$ that contain $v$ is called an $r$ -star. Then $G$ is said to be $r$ -EKR if no intersecting subfamily of $\mathcal{I}^{(r)}(G)$ is bigger than the largest $r$ -star. Let $n$ be a positive integer, and let $G$ consist of the disjoint union of $n$ paths each of length 2. We prove that if $1 \leq r \leq n/2$ , then $G$ is $r$ -EKR. This affirms a longstanding conjecture of Holroyd and Talbot for this class of graphs and can be seen as an analogue of a well-known theorem on signed sets, proved using different methods, by Deza and Frankl and by Bollobás and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest.

preprint2020arXiv

An update on reconfiguring $10$ -colorings of planar graphs

The reconfiguration graph $R_k(G)$ for the $k$ -colorings of a graph $G$ has as vertex set the set of all possible proper $k$ -colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that if $G$ is a planar graph with $n$ vertices, then $R_{12}(G)$ has diameter at most $6n$ . We improve on the number of colors, showing that $R_{10}(G)$ has diameter at most $8n$ for every planar graph $G$ with $n$ vertices.

preprint2016arXiv

Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Let $k$ , $λ$ and $μ$ be positive integers. A decomposition of a multigraph $λG$ into edge-disjoint subgraphs $G_1, \ldots , G_k$ is said to be \emph{enclosed} by a decomposition of a multigraph $μH$ into edge-disjoint subgraphs $H_1, \ldots , H_k$ if $μ> λ$ and $G_i$ is a subgraph of $H_i$ , $1 \leq i \leq k$ . In this paper we initiate the study of when a decomposition can be enclosed by a decomposition that consists of spanning subgraphs. A decomposition of a graph is a 2-factorization if each subgraph is 2-regular and is Hamiltonian if each subgraph is a Hamiltonian cycle. Let $n$ and $m$ be positive integers. We give necessary and sufficient conditions for enclosing a decomposition of $λK_n$ in a $2$ -factorization of $μK_{n+m}$ whenever $μ>λ$ and $m \geq n-2$ . We also give necessary and sufficient conditions for enclosing a decomposition of $λK_n$ in a Hamiltonian decomposition of $μK_{n+m}$ whenever $μ> λ$ and $m \geq n-1$ , or $μ> λ$ , $n=3$ and $m=1$ , or $μ= 2$ , $λ=1$ and $m=n-2$ .

preprint2016arXiv

Erdős-Ko-Rado Theorems for a Family of Trees

Given a graph $G$ and an integer $r\geq 1$ , let $\mathcal{I}^{(r)}(G)$ denote the family of independent sets of size $r$ of $G$ . For a vertex $v$ of $G$ , let $\mathcal{I}^{(r)}_v(G)$ denote the family of independent sets of size $r$ that contain~ $v$ . This family is called an $r$ -star and $v$ is the centre of the star. Then $G$ is said to be $r$ -EKR if no pairwise intersecting subfamily of $\mathcal{I}^{(r)}(G)$ is bigger than the largest $r$ -star, and if every maximum size pairwise intersecting subfamily of $\mathcal{I}^{(r)}(G)$ is an $r$ -star, then $G$ is said to be strictly $r$ -EKR. Let $μ(G)$ denote the minimum size of a maximal independent set of $G$ . Holroyd and Talbot conjectured that if $2r \leq μ(G)$ , then $G$ is $r$ -EKR and strictly $r$ -EKR if $2r < μ(G)$ . An elongated claw is a tree in which one vertex is designated the root and no vertex other than the root has degree greater than 2. A depth-two claw is an elongated claw in which every vertex of degree~1 is at distance 2 from the root. We show that if $G$ is a depth-two claw, then $G$ is strictly $r$ -EKR if $2r \leq μ(G)+1$ , confirming the conjecture of Holroyd and Talbot for this family. We also show that if $G$ is an elongated claw with $n$ leaves and at least one leaf adjacent to the root, then $G$ is $r$ -EKR if $2r \leq n$ . Hurlbert and Kamat had conjectured that one can always find a largest $r$ -star of a tree whose centre is a leaf. Baber and Borg have separately shown this to be false. We show that, moreover, for all $n \geq 2$ , $d \geq 3$ , there exists a positive integer $r$ such that there is a tree where the centre of the largest $r$ -star is a vertex of degree $n$ at distance at least $d$ from every leaf.

preprint2016arXiv

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

Let $G$ be a graph with a vertex colouring $α$ . Let $a$ and $b$ be two colours. Then a connected component of the subgraph induced by those vertices coloured either $a$ or $b$ is known as a Kempe chain. A colouring of $G$ obtained from $α$ by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of $G$ are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. A conjecture of Mohar (2007) asserts that, for $k \geq 3$ , all $k$ -colourings of a $k$ -regular graph that is not complete are Kempe equivalent. It was later shown that all $3$ -colourings of a cubic graph that is neither $K_4$ nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each $k\geq 4$ . We also report the implications of this result on the validity of the Wang-Swendsen-Kotecký algorithm for the antiferromagnetic Potts model at zero-temperature.

preprint2015arXiv

A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Let $G$ be a simple undirected graph on $n$ vertices with maximum degree~ $Δ$ . Brooks' Theorem states that $G$ has a $Δ$ -colouring unless~ $G$ is a complete graph, or a cycle with an odd number of vertices. To recolour $G$ is to obtain a new proper colouring by changing the colour of one vertex. We show an analogue of Brooks' Theorem by proving that from any $k$ -colouring, $k>Δ$ , a $Δ$ -colouring of $G$ can be obtained by a sequence of $O(n^2)$ recolourings using only the original $k$ colours unless $G$ is a complete graph or a cycle with an odd number of vertices, or $k=Δ+1$ , $G$ is $Δ$ -regular and, for each vertex $v$ in $G$ , no two neighbours of $v$ are coloured alike. We use this result to study the reconfiguration graph $R_k(G)$ of the $k$ -colourings of $G$ . The vertex set of $R_k(G)$ is the set of all possible $k$ -colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. We prove that for $Δ\geq 3$ , $R_{Δ+1}(G)$ consists of isolated vertices and at most one further component which has diameter $O(n^2)$ . This result enables us to complete both a structural classification and an algorithmic classification for reconfigurations of colourings of graphs of bounded maximum degree.

preprint2015arXiv

Kempe Equivalence of Colourings of Cubic Graphs

Given a graph $G=(V,E)$ and a proper vertex colouring of $G$ , a Kempe chain is a subset of $V$ that induces a maximal connected subgraph of $G$ in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by exchanging the colours of vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe changes. A conjecture of Mohar asserts that, for $k \geq 3$ , all $k$ -colourings of $k$ -regular graphs that are not complete are Kempe equivalent. We address the case $k=3$ by showing that all $3$ -colourings of a cubic graph $G$ are Kempe equivalent unless $G$ is the complete graph $K_4$ or the triangular prism.

preprint2015arXiv

Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph

A graph $G = (V, E)$ is \emph{partitionable} if there exists a partition $\{A, B\}$ of $V$ such that $A$ induces a disjoint union of cliques and $B$ induces a triangle-free graph. In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be $\NP$-complete on arbitrary graphs. Here it is proved that if a graph $G$ is bull-free, planar, perfect, $K_4$ -free or does not contain certain holes then deciding whether $G$ is partitionable is $\NP$-complete. This answers an open question posed by Thomass{é}, Trotignon and Vuškovi{ć}. In contrast a finite list of forbidden induced subgraphs is given for partitionable cographs.

preprint2014arXiv

NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be $\NP$-complete on arbitrary graphs. We show that this problem remains $\NP$-complete even when restricted to planar graphs and perfect 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.

Carl Feghali

Research overview

Is this your work?

16 publications

Solution to a problem of Katona on counting cliques of weighted graphs

1-Extendability of independent sets

A note on Matching-Cut in $P_t$ -free Graphs

Kempe equivalence of $4$ -critical planar graphs

Strengthening a theorem of Meyniel

The maximum sum of sizes of cross-intersecting families of subsets of a set

A Thomassen-type method for planar graph recoloring

An Erdős-Ko-Rado Theorem for unions of length 2 paths

An update on reconfiguring $10$ -colorings of planar graphs

Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Erdős-Ko-Rado Theorems for a Family of Trees

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Kempe Equivalence of Colourings of Cubic Graphs

Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph

NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

See the researcher in context

Building this map preview

Carl Feghali

Research overview

Is this your work?

16 publications

Solution to a problem of Katona on counting cliques of weighted graphs

1-Extendability of independent sets

A note on Matching-Cut in PtP_tPt​-free Graphs

Kempe equivalence of 444-critical planar graphs

Strengthening a theorem of Meyniel

The maximum sum of sizes of cross-intersecting families of subsets of a set

A Thomassen-type method for planar graph recoloring

An Erdős-Ko-Rado Theorem for unions of length 2 paths

An update on reconfiguring 101010-colorings of planar graphs

Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Erdős-Ko-Rado Theorems for a Family of Trees

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Kempe Equivalence of Colourings of Cubic Graphs

Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph

NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

See the researcher in context

Building this map preview

A note on Matching-Cut in $P_t$ -free Graphs

Kempe equivalence of $4$ -critical planar graphs

An update on reconfiguring $10$ -colorings of planar graphs