Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Structured Table of Graphs with Symmetries and Other Special Properties
48
0
0.0
(
0
)
Added by
Zhipeng Xu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We organize a table of regular graphs with minimal diameters and minimal mean path lengths, large bisection widths and high degrees of symmetries, obtained by enumerations on supercomputers. These optimal graphs, many of which are newly discovered, may find wide applications, for example, in design of network topologies.
rate research
Read More
The second authors $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chi leq lceil frac 12 (Delta+1+omega)rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful $chi$-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and sufficiently high degree, we prove the NP-completeness of acyclic r-colorings; our method also implies the known analogue for classical colorings. The proofs use high girth graphs with high arboricity and dichromatic numbers. High girth graphs and digraphs with high chromatic and dichromatic numbers have been well studied; we re-derive the results from a general result about relational systems, which also implies the similar fact about high girth and high arboricity used in the proofs. These facts concern graphs and digraphs of high girth and low degree; we contrast them by considering acyclic colorings of tournaments (which have low girth and high degree). We prove that even though acyclic two-colorability of tournaments is known to be NP-complete, random acyclically r-colorable tournaments allow recovering an acyclic r-coloring in deterministic linear time, with high probablity.
A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$. We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$: (a) $mathrm{dim}_{COG}(G)leqmathrm{tw}(G)+2$, (b) $mathrm{dim}_{TH}(G)leqmathrm{pw}(G)+1$, and (c) $mathrm{dim}_{TH}(G)leqchi(G)cdotmathrm{box}(G)$, where $mathrm{tw}(G)$, $mathrm{pw}(G)$, $chi(G)$ and $mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$. We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $mathrm{dim}_{COG}(G)$ and $mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes.
This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences.
An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama emph{et al.}~citep{ds05} proved that every graph with maximum average degree strictly less than $3$ can be incidence colored with $Delta+3$ colors. Recently, Bonamy emph{et al.}~citep{Bonamy} proved that every graph with maximum degree at least $4$ and with maximum average degree strictly less than $frac{7}{3}$ admits an incidence $(Delta+1)$-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between $4$ and $6$. In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree less than $4$ admits an incidence $(Delta+3)$-coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Delta+3)$-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Delta + 7)$-coloring. More generally, we prove that $Delta+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
