16 citations · 48 across the 24 of their papers we have counts for
14 papers · 1 filter
On the structure of (, , )-free graphs
Chính T. Hoàng, Ramin Javadi, Nicolas Trotignon
Determining the complexity of colouring ()-free graph is a long open problem. Recently Penev showed that there is a polynomial-time algorithm to colour a ($4K_1, C_4, C_…
A class of graphs with large rankwidth
Chính Hoàng, Nicolas Trotignon
We describe several graphs with arbitrarily large rankwidth (or equivalently with arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, Graphs…
The intersection of two vertex coloring problems
Angele M. Foley, Dallas J. Fraser, Chinh T. Hoang +2
A hole is an induced cycle with at least four vertices. A hole is even if its number of vertices is even. Given a set L of graphs, a graph G is L-free if G does not contain any gra…
Solving the clique cover problem on (bull, )-free graphs
Kathie Cameron, Chính T. Hoàng
We give an algorithm to find a minimum clique cover of a (bull, )-free graph, or equivalently, a minimum colouring of a (bull, )-free graph, where is the nu…
On the structure of (pan, even hole)-free graphs
Kathie Cameron, Steven Chaplick, Chinh T. Hoang
A hole is a chordless cycle with at least four vertices. A pan is a graph which consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a ho…
Polynomial-time algorithms for minimum weighted colorings of ()-free graphs and related graph classes
Chính T. Hoàng, D. Adam Lazzarato
We design an algorithm to find a minimum weighted coloring of a ()-free graph. Furthermore, the same technique can be used to solve the same problem for se…
Edge Intersection Graphs of L-Shaped Paths in Grids
Kathie Cameron, Steven Chaplick, Chính T. Hoàng
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 re…
A characterization of b-perfect graphs
Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek
A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number of a g…
Finding a sun in building-free graphs
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3},…
On graphs without a C4 or a diamond
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for…
A certifying algorithm for 3-colorability of P5-free graphs
Daniel Bruce, Chinh T. Hoang, Joe Sawada
We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colo…
Asteroids in rooted and directed path graphs
Kathie Cameron, Chinh Hoàng, Benjamin Lévêque
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central r…
On the complexity of finding a sun in a graph
Chinh T. Hoang
The sun is the graph obtained from a cycle of length even and at least six by adding edges to make the even-indexed vertices pairwise adjacent. Suns play an important role in the s…
k-Colorability of P5-free graphs
C. T. Hoang, J. Sawada, X. Shu
A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorit…