Source author record

Kathie Cameron

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

$k$ -Critical Graphs in $P_5$ -Free Graphs

Given two graphs $H_1$ and $H_2$ , a graph $G$ is $(H_1,H_2)$ -free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$ . Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$ -vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$ . The study of $k$ -vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$ -colorable. In this paper, we initiate a systematic study of the finiteness of $k$ -vertex-critical graphs in subclasses of $P_5$ -free graphs. Our main result is a complete classification of the finiteness of $k$ -vertex-critical graphs in the class of $(P_5,H)$ -free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworth's Theorem -- that may be of independent interest.

preprint2016arXiv

Structure and algorithms for (cap, even hole)-free graphs

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}ω(G) -1$ , and hence $χ(G)\leq \frac{3}{2}ω(G)$ , where $ω(G)$ denotes the size of a largest clique in $G$ and $χ(G)$ denotes the chromatic number of $G$ . We give an $O(nm)$ algorithm for $q$ -coloring these graphs for fixed $q$ and an $O(nm)$ algorithm for maximum weight stable set. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6ω(G)-1$ and clique-width at most 48.

preprint2014arXiv

Edge Intersection Graphs of L-Shaped Paths in Grids

In this paper we continue the study of the edge intersection graphs of one (or zero) bend paths on a rectangular grid. That is, the edge intersection graphs where each vertex is represented by one of the following shapes: $\llcorner$ , $\ulcorner$ , $\urcorner$ , $\lrcorner$ , and we consider zero bend paths (i.e., | and $-$ ) to be degenerate $\llcorner$ s. These graphs, called $B_1$ -EPG graphs, were first introduced by Golumbic et al (2009). We consider the natural subclasses of $B_1$ -EPG formed by the subsets of the four single bend shapes (i.e., { $\llcorner$ }, { $\llcorner$ , $\ulcorner$ }, { $\llcorner$ , $\urcorner$ }, and { $\llcorner$ , $\ulcorner$ , $\urcorner$ }) and we denote the classes by [ $\llcorner$ ], [ $\llcorner$ , $\ulcorner$ ], [ $\llcorner$ , $\urcorner$ ], and [ $\llcorner$ , $\ulcorner$ , $\urcorner$ ] respectively. Note: all other subsets are isomorphic to these up to 90 degree rotation. We show that testing for membership in each of these classes is NP-complete and observe the expected strict inclusions and incomparability (i.e., [ $\llcorner$ ] $\subsetneq$ [ $\llcorner$ , $\ulcorner$ ], [ $\llcorner$ , $\urcorner$ ] $\subsetneq$ [ $\llcorner$ , $\ulcorner$ , $\urcorner$ ] $\subsetneq$ $B_1$ -EPG; also, [ $\llcorner$ , $\ulcorner$ ] is incomparable with [ $\llcorner$ , $\urcorner$ ]). Additionally, we give characterizations and polytime recognition algorithms for special subclasses of Split $\cap$ [ $\llcorner$ ].

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.

Kathie Cameron

Research overview

Is this your work?

3 publications

$k$ -Critical Graphs in $P_5$ -Free Graphs

Structure and algorithms for (cap, even hole)-free graphs

Edge Intersection Graphs of L-Shaped Paths in Grids

See the researcher in context

Building this map preview

Kathie Cameron

Research overview

Is this your work?

3 publications

kkk-Critical Graphs in P5P_5P5​-Free Graphs

Structure and algorithms for (cap, even hole)-free graphs

Edge Intersection Graphs of L-Shaped Paths in Grids

See the researcher in context

Building this map preview

$k$ -Critical Graphs in $P_5$ -Free Graphs