Do you want to publish a course? Click here

$(1, k)$-coloring of graphs with girth at least $5$ on a surface

232   0   0.0 ( 0 )
 Added by Ilkyoo Choi
 Publication date 2014
  fields
and research's language is English




Ask ChatGPT about the research

A graph is $(d_1, ..., d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $iin {1, ..., r}$. For a given pair $(g, d_1)$, the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $gamma$, there exists a $K=K(gamma)$ where graphs with girth at least $5$ that are embeddable on $S$ are $(1, K)$-colorable. On the other hand, there is no finite $k$ where planar graphs (and thus embeddable on any surface) with girth at least $5$ are $(0, k)$-colorable.



rate research

Read More

In this paper we obtain $(q+3)$--regular graphs of girth 5 with fewer vertices than previously known ones for $q=13,17,19$ and for any prime $q ge 23$ performing operations of reductions and amalgams on the Levi graph $B_q$ of an elliptic semiplane of type ${cal C}$. We also obtain a 13-regular graph of girth 5 on 236 vertices from $B_{11}$ using the same technique.
In this paper we are interested in the {it{Cage Problem}} that consists in constructing regular graphs of given girth $g$ and minimum order. We focus on girth $g=5$, where cages are known only for degrees $k le 7$. We construct regular graphs of girth $5$ using techniques exposed by Funk [Note di Matematica. 29 suppl.1, (2009) 91 - 114] and Abreu et al. [Discrete Math. 312 (2012), 2832 - 2842] to obtain the best upper bounds known hitherto. The tables given in the introduction show the improvements obtained with our results.
In this paper, we show that all fat Hoffman graphs with smallest eigenvalue at least -1-tau, where tau is the golden ratio, can be described by a finite set of fat (-1-tau)-irreducible Hoffman graphs. In the terminology of Woo and Neumaier, we mean that every fat Hoffman graph with smallest eigenvalue at least -1-tau is an H-line graph, where H is the set of isomorphism classes of maximal fat (-1-tau)-irreducible Hoffman graphs. It turns out that there are 37 fat (-1-tau)-irreducible Hoffman graphs, up to isomorphism.
The $(n-ell)$-deck of an $n$-vertex graph is the multiset of subgraphs obtained from it by deleting $ell$ vertices. A family of $n$-vertex graphs is $ell$-recognizable if every graph having the same $(n-ell)$-deck as a graph in the family is also in the family. We prove that the family of $n$-vertex graphs having no cycles is $ell$-recognizable when $nge2ell+1$ (except for $(n,ell)=(5,2)$). It is known that this fails when $n=2ell$.
In this note we construct a new infinite family of $(q-1)$-regular graphs of girth $8$ and order $2q(q-1)^2$ for all prime powers $qge 16$, which are the smallest known so far whenever $q-1$ is not a prime power or a prime power plus one itself.
comments
Fetching comments Fetching comments
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا