Source author record

Cláudia Linhares Sales

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

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On the b-continuity of the lexicographic product of graphs

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of $G$ is the maximum integer $χ_b(G)$ for which $G$ has a b-coloring with $χ_b(G)$ colors. A graph $G$ is b-continuous if $G$ has a b-coloring with $k$ colors, for every integer $k$ in the interval $[χ(G),χ_b(G)]$ . It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product $G[H]$ of b-continuous graphs $G$ and $H$ is also b-continuous. Using homomorphisms, we provide a new lower bound for $χ_b(G[H])$ , namely $χ_b(G[K_t])$ , where $t=χ_b(H)$ , and prove that if $G[K_\ell]$ is b-continuous for every positive integer $\ell$ , then $G[H]$ admits a b-coloring with $k$ colors, for every $k$ in the interval $[χ(G[H]),χ_b(G[K_t])]$ . We also prove that $G[K_\ell]$ is b-continuous, for every positive integer $\ell$ , whenever $G$ is a $P_4$ -sparse graph, and we give further results on the b-spectrum of $G[K_\ell]$ , when $G$ is chordal.

preprint2016arXiv

Proper Orientations of Planar Bipartite Graphs

An orientation of a graph $G$ is proper if any two adjacent vertices have different indegrees. The proper orientation number $\overrightarrowχ(G)$ of a graph $G$ is the minimum of the maximum indegree, taken over all proper orientations of $G$ . In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that $\overrightarrowχ(G) \leq 4$ , when $G$ is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.

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.