Source author record

Mathew C. Francis

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

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs

Hadwiger's conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwiger's conjecture is true for line graphs. We investigate this conjecture on the closely related class of total graphs. The total graph of $G$ , denoted by $T(G)$ , is defined on the vertex set $V(G)\sqcup E(G)$ with $c_1,c_2\in V(G)\sqcup E(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incident on each other in $G$ . We first show that there exists a constant $C$ such that, if the connectivity of $G$ is at least $C$ , then Hadwiger's conjecture is true for $T(G)$ . The total chromatic number $χ"(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $χ"(G)=χ(T(G))$ . Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$ , $χ"(G)\leqΔ(G)+2$ , where $Δ(G)$ is the maximum degree of $G$ . We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $χ"(G)\leqΔ(G)+3$ , is true for a class of graphs $\mathcal{F}$ that is closed under the operation of taking subgraphs, then Hadwiger's conjecture is true for the class of total graphs of graphs in $\mathcal{F}$ . This motivated us to look for classes of graphs that satisfy weak TCC. It may be noted that a complete proof of TCC for even 4-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak TCC can be proved easily for 4-colorable graphs. We noticed that in spite of the interest in studying $χ"(G)$ in terms of $χ(G)$ right from the initial days, weak TCC is not proven to be true for $k$ -colorable graphs even for $k=5$ . In the second half of the paper, we make a contribution to the literature on total coloring by proving that $χ"(G)\leqΔ(G)+3$ for every 5-colorable graph $G$ .

preprint2020arXiv

Representing graphs as the intersection of cographs and threshold graphs

A graph $G$ is said to be the intersection of graphs $G_1,G_2,\ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=\cdots=V(G_k)$ and $E(G)=E(G_1)\cap E(G_2)\cap\cdots\cap E(G_k)$ . For a graph $G$ , $\mathrm{dim}_{COG}(G)$ (resp. $\mathrm{dim}_{TH}(G)$ ) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$ . We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$ : (a) $\mathrm{dim}_{COG}(G)\leq\mathrm{tw}(G)+2$ , (b) $\mathrm{dim}_{TH}(G)\leq\mathrm{pw}(G)+1$ , and (c) $\mathrm{dim}_{TH}(G)\leqχ(G)\cdot\mathrm{box}(G)$ , where $\mathrm{tw}(G)$ , $\mathrm{pw}(G)$ , $χ(G)$ and $\mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$ . We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $\mathrm{dim}_{COG}(G)$ and $\mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes.

preprint2016arXiv

Uniquely Restricted Matchings in Interval Graphs

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$ . We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. ("Uniquely restricted matchings", M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality "strong independent set" in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.

preprint2013arXiv

Strong chromatic index of chordless graphs

A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$ , denoted by $χ'_s(G)$ , is the minimum number of colours needed in any strong edge colouring of $G$ . A graph is said to be \emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Δ$ , then $χ'_s(G) \leq 8Δ-6$ . We improve this result by showing that for every chordless graph $G$ with maximum degree $Δ$ , $χ'_s(G)\leq 3Δ$ . This bound is tight up to to an additive constant.

preprint2012arXiv

The Maximum Clique Problem in Multiple Interval Graphs

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$ -interval graphs when $t\geq 3$ and polynomial-time solvable when $t=1$ . The problem is also known to be NP-complete in $t$ -track graphs when $t\geq 4$ and polynomial-time solvable when $t\leq 2$ . We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$ -circular interval graphs and $t$ -circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$ -approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$ -interval graphs, improving earlier work with approximation ratio $4t$ .

preprint2010arXiv

Segment representation of a subclass of co-planar graphs

A graph is said to be a segment graph if its vertices can be mapped to line segments in the plane such that two vertices have an edge between them if and only if their corresponding line segments intersect. Kratochvíl and Kuběna [``On intersection representations of co-planar graphs'', Discrete Mathematics, 178(1-3):251-255, 1998] asked the question of whether the complements of planar graphs are segment graphs. We show here that the complements of all partial 2-trees are segment 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.