Source author record

Julio Araujo

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

Circular Backbone Colorings: on matching and tree backbones of planar graphs

Given a graph $G$ , and a spanning subgraph $H$ of $G$ , a circular $q$ -backbone $k$ -coloring of $(G,H)$ is a proper $k$ -coloring $c$ of $G$ such that $q\le \lvert c(u)-c(v)\rvert \le k-q$ , for every edge $uv\in E(H)$ . The circular $q$ -backbone chromatic number of $(G,H)$ , denoted by $CBC_q(G,H)$ , is the minimum integer $k$ for which there exists a circular $q$ -backbone $k$ -coloring of $(G,H)$ . The Four Color Theorem implies that whenever $G$ is planar, we have $CBC_2(G,H)\le 8$ . It is conjectured that this upper bound can be improved to 7 when $H$ is a tree, and to 6 when $H$ is a matching. In this work, we show that: 1) if $G$ is planar and has no $C_4$ as subgraph, and $H$ is a linear spanning forest of $G$ , then $CBC_2(G,H)\leq 7$ ; 2) if $G$ is a plane graph having no two 3-faces sharing an edge, and $H$ is a matching of $G$ , then $CBC_2(G,H)\leq 6$ ; and 3) if $G$ is planar and has no $C_4$ nor $C_5$ as subgraph, and $H$ is a mathing of $G$ , then $CBC_2(G,H)\leq 5$ . These results partially answer questions posed by Broersma, Fujisawa and Yoshimoto (2003), and by Broersma, Fomin and Golovach (2007). It also points towards a positive answer for the Steinberg's Conjecture.

preprint2015arXiv

On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring

A proper $k$ -coloring of a graph $G=(V,E)$ is a function $c: V(G)\to \{1,\ldots,k\}$ such that $c(u)\neq c(v)$ , for every $uv\in E(G)$ . The chromatic number $χ(G)$ is the minimum $k$ such that there exists a proper $k$ -coloring of $G$ . Given a spanning subgraph $H$ of $G$ , a $q$ -backbone $k$ -coloring of $(G,H)$ is a proper $k$ -coloring $c$ of $V(G)$ such that $\lvert c(u)-c(v)\rvert \ge q$ , for every edge $uv\in E(H)$ . The $q$ -backbone chromatic number $BBC_q(G,H)$ is the smallest $k$ for which there exists a $q$ -backbone $k$ -coloring of $(G,H)$ . In this work, we show that every connected graph $G$ has a generating tree $T$ such that $BBC_q(G,T) = \max\{χ(G),\left\lceil\frac{χ(G)}{2}\right\rceil+q\}$ , and that this value is the best possible. As a direct consequence, we get that every connected graph $G$ has a spanning tree $T$ for which $BBC_2(G,T)=χ(G)$ , if $χ(G)\ge 4$ , or $BBC_2(G,T)=χ(G)+1$ , otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph $G$ has a spanning tree $T$ such that $BBC_2(G,T)=4$ . This settles a question by Wang, Bu, Montassier and Raspaud (2012), and generalizes a number of previous partial results to their question.

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.