ML p(r)ior | The b-continuity of graphs with large girth

The b-continuity of graphs with large girth

2016-02-03
1602.01298 | math.CO
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 $[\chi(G),b(G)]$. It is known that not all graphs are b-continuous. In this article, we show that if $G$ has girth at least 10, then $G$ is b-continuous.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-05-15
1905.06293 | cs.DM

A perfect Italian dominating function of a graph $G=(V,E)$ is a function $f : V \to \{0,1,2\}$ such … show more
PDF

Highlights - Most important sentences from the article

2019-03-07
1903.03197 | cs.DM

A graph G is called well-indumatched if all of its maximal induced matchings have the same size. In … show more
PDF

Highlights - Most important sentences from the article

2018-10-18

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\"os, Si… show more
PDF

Highlights - Most important sentences from the article

2018-11-09
1811.03966 | cs.DS

A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contai… show more
PDF

Highlights - Most important sentences from the article

2017-02-28

In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked i… show more
PDF

Highlights - Most important sentences from the article

2018-11-09

The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorph… show more
PDF

Highlights - Most important sentences from the article

2016-05-29
1605.09055 | math.CO

If a graph has $n\ge4k$ vertices and more than $n^2/4$ edges, then it contains a copy of $C_{2k+1}$.… show more
PDF

Highlights - Most important sentences from the article

2018-02-15

This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as f… show more
PDF

Highlights - Most important sentences from the article

2018-12-23

Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each we… show more
PDF

Highlights - Most important sentences from the article

2018-07-24
1807.09034 | math.CO

A connected ordering $(v_1, v_2, \ldots, v_n)$ of $V(G)$ is an ordering of the vertices such that $v… show more
PDF

Highlights - Most important sentences from the article

2018-09-21
1809.08140 | math.CO

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs … show more
PDF

Highlights - Most important sentences from the article

2019-02-19
1902.07241 | math.CO

This paper serves as the first extension of the topic of dominator colorings of graphs to the settin… show more
PDF

Highlights - Most important sentences from the article

2018-02-27

Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bo… show more
PDF

Highlights - Most important sentences from the article

2018-10-01

For a graph $G$ and integer $q\geq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edg… show more
PDF

Highlights - Most important sentences from the article

2017-10-21

We study the problem of determining whether a given graph~$G=(V,E)$ admits a matching~$M$ whose remo… show more
PDF

Highlights - Most important sentences from the article

2018-01-11

In Defective Coloring we are given a graph $G = (V, E)$ and two integers $\chi_d, \Delta^*$ and are … show more
PDF

Highlights - Most important sentences from the article